Hidden Enchantment
While researching the history of the One Ring, Gandalf is puzzled by a mysterious passage in an ancient book. Parts of the passage seems to possess similarities to the words for an enchantment for invisibility, but with many missing and extra letters. To compare the two letter sequences, Gandalf decides to make a rectangular drawing constructed as follows:
The mysterious book passage is placed at the top of the drawing, running from
left to right. The words for the enchantment are placed at the left of the
drawing, running from top to bottom. When letters from the two sequences match,
a letter x
is placed in the drawing at the point where the letters
intersect when lines (running either top-to-bottom or left-to-right) are drawn
through the two letters. If three or more letters in a row (in the two
sequences) match, a letter Q
is drawn for each of the matches instead
(note these matches form diagonals heading to the bottom right). A period
.
is drawn for every mismatch. For instance, the two sequences
ring
and grin
would produce the following drawing, with an
x
for the matching g
, and Q
for the matching
rin
:
ring
----
g|...x
r|Q...
i|.Q..
n|..Q.
The comparison is case-sensitive, so r
matches r
but not
R
. Once the drawing is complete, Gandalf can discover which sections of
the book's mysterious passage match words in the enchantment by looking for
long diagonal runs of Q
s in the drawing.
Input Format
The input is simply the two sequences of letters, each on a separate line. The book passage comes first, followed by the enchantment. You may assume that the longest length for either sequence is at most 75 letters.
Output Format
The drawing representing the comparison is as follows. The first row contains
the book passage, beginning at the 3rd column (passage is preceded by 2
spaces). The second row is a row of dashes the same length as the passage, also
starting at the 3rd column. The third and succeeding rows conta in the
enchantment and matches. The enchantment is displayed vertically in the
first column, starting in the 3rd row. The second column is a row of vertical
bars, the same length as the enchantment. The remaining columns are the
matches/mismatches represented by x
, Q
, and .
s.
Examples
Input 1:
ThisIsTheOneRing OneRingToFindThem
Output 1:
ThisIsTheOneRing ---------------- O|.........Q...... n|..........Q...x. e|........x..Q.... R|............Q... i|..x..........Q.. n|..........x...Q. g|...............Q T|x.....x......... o|................ F|................ i|..x..........x.. n|..........x...x. d|................ T|x.....Q......... h|.x.....Q........ e|........Q..x.... m|................
Input 2:
OneRingToRuleThemAll,OneRingToFindThem OneRingToBringThemAll,AndInTheDarknessBindThem
Output 2:
OneRingToRuleThemAll,OneRingToFindThem -------------------------------------- O|Q....................Q................ n|.Q...x................Q...x.....x..... e|..Q.........x..x.......Q............x. R|...Q.....x..............Q............. i|....Q....................Q.....x...... n|.x...Q................x...Q.....x..... g|......Q....................Q.......... T|.......Q.....x..............Q.....x... o|........Q....................Q........ B|...................................... r|...................................... i|....Q....................Q.....x...... n|.x...Q................x...Q.....x..... g|......Q....................Q.......... T|.......Q.....Q..............Q.....Q... h|..............Q....................Q.. e|..x.........x..Q.......x............Q. m|................Q....................Q A|.................Q.................... l|...........x......Qx.................. l|...........x......xQ.................. ,|....................Q................. A|.................x.................... n|.x...x................x...x.....x..... d|.................................x.... I|...................................... n|.x...x................x...x.....x..... T|.......x.....Q..............x.....Q... h|..............Q....................Q.. e|..x.........x..Q.......x............Q. D|...................................... a|...................................... r|...................................... k|...................................... n|.x...x................x...x.....x..... e|..x.........x..x.......x............x. s|...................................... s|...................................... B|...................................... i|....x....................x.....Q...... n|.x...x................x...x.....Q..... d|.................................Q.... T|.......x.....Q..............x.....Q... h|..............Q....................Q.. e|..x.........x..Q.......x............Q. m|................Q....................Q
Test Data
-
The file sample.txt should produce the following output:
-
The file sample2.txt should produce the following output: