Diff

In computing, diff is a file comparison utility that outputs the differences between two files. It is typically used to show the changes between a file and a former version of the same file. Diff displays the changes made per line for text files.
The operation of diff is based on solving the longest common subsequence problem which is as follows: Given two sequences A = a1, a2, ..., aM, and B = b1, b2, ..., bN, find the length, k, of the longest sequence C = c1, c2, ..., ck such that C is a subsequence of both A and B. As an example, if
A = d, y, n, a, m, i, c and B = p, r, o, g, r, a, m, m, i, n, g
then the longest common subsequence is a, m, i( {3,4,5} from A, {5,6,8} from B) and has length 3.
You may find {5,7,8} from B is also a, m, i, but {5,6,8} is lexicographic smaller, so we choose the former one. We always choose the lexicographic smallest one.
From the longest common subsequence it's only a small step to get diff-like output:
dyn-progr+m+c-ng+
where '-' means a deletion from and '+' means an addition to the first string.
Now you are supposed to simulate the diff operation.

Your program must read test cases from standard input.
The input file consists of several test cases. Each case contains the contents of two files. The case starts with two non-negative integers N and M (both <= 50), then followed by N+M lines, each contains a string of no more than 80 characters. The first N lines are the contents of the first file, while the second M lines are of the second file.
The input is finished by a negative N.

For each test case, your program must output to standard output. If there is no difference found between the two files, print in a line "No difference found". If there is nothing in common between the two files, print in a line "Totally different". Otherwise, first print in a line the length of the longest sequence. Then for each line of the first file, print the line number, and output the differences in the diff-like format line by line, as shown by the sample output.

1 1
This is a test
This is a test
1 1
ab
cd
1 1
dynamic
programming
4 4
This is a test
which is more complicated
zzz
than ...
This is another test
of the project
which is much more complex
than the previous one
-100

No difference found
Totally different
3
line #1
dyn-progr+m+c-ng+
39
line #1
nother+
line #2
of the project+
uch m+icat-d-
line #3
zzz-
line #4
x+
...-the previous one+

浙大计算机研究生保研复试上机考试-2011年