hdu1238

maksyuki 发表于 oj 分类,标签:
0

Substrings

Problem Description

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

2

3

ABCD

BCDFF

BRCD

2

rose

orchid

Sample Output

2

2

Author

Asia 2002, Tehran (Iran), Preliminary

 

题目类型:字符串处理

算法分析:首先找到给出的字符串组中长度最小的那一个,然后从大到小枚举该字符串的所有子串,对于每个子串,判断它和它的反转串是否在其他的字符串中存在,如果都存在一种情况(正串或者是反串),则退出判断,输出结果