Substrings(HDU-1238)
题面
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.
输入
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.
输出
There should be one line per test case containing the length of the largest string found.
样例输入
12
23
3ABCD
4BCDFF
5BRCD
62
7rose
8orchid样例输出
12
22提示
无
思路
枚举子串，暴力KMP即可。
代码
1char s[105][mxn], t[mxn], t2[mxn];
2int nxt[mxn], nxt2[mxn], len[mxn];
3
4void getnxt(char* t, int m)
5{
6 int i = 0, j = -1; nxt[0] = -1;
7 while (i < m)
8 {
9 if (j == -1 || t[i] == t[j]) {
10 i++, j++;
11 // if (t[i] == t[j])
12 // nxt[i] = nxt[j]; // next数组优化
13 // else
14 nxt[i] = j;
15 } else
16 j = nxt[j];
17 }
18}
19
20int KMP(char* s, char* t, int n, int m)
21{
22 int i = 0, j = 0, ans = 0;
23 while (i < n)
24 {
25 if (j == -1 || s[i] == t[j]) {
26 i++, j++;
27 if (j >= m) { // 匹配
28 // ans++;
29 // j = nxt[j];
30 return i-j;
31 }
32 } else
33 j = nxt[j];
34 }
35 // return ans;
36 return -1;
37}
38
39int main()
40{
41 int T; scanf("%d", &T);
42 while(T--)
43 {
44 int n; scanf("%d", &n);
45 for(int i=0; i<n; i++){
46 scanf("%s", s[i]);
47 len[i] = strlen(s[i]);
48 }
49 int ans=0;
50 for(int i=0; i<len[0]; i++) // 枚举模式串起点
51 {
52 int tl = 0, k;
53 for(int j=i; j<len[0]; j++) // 枚举模式串长度
54 {
55 t[tl++] = s[0][j];
56 for(int x=0; x<tl; x++) t2[x] = t[tl-x-1];
57 t[tl] = t2[tl] = '\0';
58 getnxt(t, tl);
59 getnxt(t2, tl);
60 for(k=0; k<n; k++) // 枚举所有文本串
61 if(KMP(s[k], t, len[k], tl) == -1 && KMP(s[k], t2, len[k], tl) == -1)
62 break;
63 if(k>=n) // 满足条件
64 ans = max(ans, tl);
65 }
66 }
67 printf("%d\n", ans);
68 }
69 return 0;
70}