|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
Description
The words "waterproof" and "proofreading" have a common part "proof", which is the prefix of "proofreading" and the suffix of "waterproof". Given all possible pairs extracted from a list of words, your task is to find the length of the common suffix-prefix of a pair that is the longest one.
For example, if the list consists of "proofreading", "waterproof", and "ingredient", then the answer will be 5, since the common suffix-prefix for the pair of "waterproof" and "proofreading" contains 5 letters and is the longest, in comparison with the common suffix-prefix for the pair of "proofreading" and "ingredient", which is "ing" and has only 3 letters.
Input
The first line is an integer T (T <= 100) denoting the number of test cases. Each case starts with an integer N indicating the number of words. The next N strings are the list of the words for this test case. Each word has at most M letters, all in lower-case.
case 1: 2 <= N <= 10, 1 <= M <= 15
case 2: 2 <= N <= 20, 1 <= M <= 15
case 3: 2 <= N <= 20, 1 <= M <= 30
case 4: 2 <= N <= 30, 1 <= M <= 30
Output
The output should contain T lines for the T cases. Each line shows an integer that represents the longest length of the common part for the best choice of word pair.
Tags