The longest common subsequence problem (LCS) is finding the longest subsequence common to all sequences in a set of sequences (often just two). It is a classic computer science problem, the basis of diff, and has applications in bioinformatics.
Given a set of sequences, output the length of the LCS of these sequences.
Each test case starts by a number n (1<=n<=100), denoting the number of sequences. Following are n sequences, each on a line. These sequences contain lower-case letters only and have a maximum length of 15.
For each test case, output the length of the LCS on a line by itself.
2 abcd dcba 3 abcdefg deiscool imde
1 2
In case n=2, there is a dynamic programming solution. But now n may be larger than 2.
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|