Project 5: Diff

p5

go to the 1st comment for the problem statement please. :)

Project 5: Diff

Given two strings S₁ and S₂, find the LCS (longest common subsequence) of them.

Input Specification

There is only one input file and it contains multiple test cases. The first line of input file contains one positive integer T, indicating there are T test cases. For each test case, there are two lines. Each line contains one string S_i (1 <= |S_i| <= 1000, |S_i| means the length of S_i). All characters in S_i are printable standard ASCII characters, which means all in the range [0x20, 0x7E]. Please note that S_i may contain spaces since the ASCII code of space (' ') is 0x20. It's case sensitive in this problem, so 'A' and 'a' should be treated as different characters.

Output Specification

For each test case:

• If the two strings are totally the same, output No difference found.
• If there are nothing in common between them, output Totally different.
• Otherwise, first print one integer N in a line indicating the length of LCS and then two lines follow. The i^th line contains L integers in increasing order, separated by one space, indicating the indices (1-based) of characters in S_i that also appear in LCS. If there are multiple different LCS, printing any of them is accepted.

Don't output redundant characters like spaces at the front or the end of a line.

Sample Input

6
abc
abc
abc
xyz
dynamic
programming
abc
bac
2015 ACM-ICPC world finals are held in Morocco!
ICPC is International Collegiate Programming Contest.
$ g++ hello_world.c -Wall -o hello_world && ./a.out
Hello World!

Sample Output

No difference found
Totally different
3
4 5 6
6 8 9
2
2 3
1 3
18
10 11 12 13 14 20 22 23 24 25 27 30 33 36 37 38 39 46
1 2 3 4 5 8 17 19 20 21 22 27 32 33 42 43 45 47
10
8 9 10 14 20 22 37 38 39 40
2 3 4 5 6 7 8 9 10 11

Hint

In the 3^rd test case, following output is also accepted:

3
4 5 6
6 8 9

In the 4^th test case, following output is also accepted:

2
2 3
1 3