http://acm.hdu.edu.cn/showproblem.php?pid=1238
Substrings
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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
之前写个是完全的暴力写的，因为数据很小，暴力也没关系，这次用了KMP，有点小题大做的感觉，不过刚刚学，就当练习了。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MOD 10000
#define N 210 char s[N][N];
int Next[N]; void FindNext(char b[])
{
int i=, j=-, blen=strlen(b);
Next[] = -; while(i<blen)
{
if(j==- || b[i]==b[j])
Next[++i] = ++j;
else
j = Next[j];
}
} int KMP(char a[], char b[])
{
int i=, j=;
int alen=strlen(a), blen=strlen(b); FindNext(b); while(i<alen)
{
while(j==- || (a[i]==b[j] && i<alen && j<blen))
i++, j++;
if(j==blen)
return ;
j = Next[j];
}
return ;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int i, j, k, n, MinLen=, len;
char ss[N]; memset(s, , sizeof(s)); scanf("%d", &n); for(i=; i<n; i++)
{
scanf("%s", s[i]);
len = strlen(s[i]); if(len<MinLen)
{
MinLen = len;
memset(ss, , sizeof(ss));
strcpy(ss, s[i]);
}
} char a[N], b[N];
int index=; for(i=MinLen; i>; i--)
for(j=; j<=MinLen-i; j++)
{
memset(a, , sizeof(a));
memset(b, , sizeof(b));
strncpy(a, ss+j, i);
strcpy(b, a);
strrev(b); for(k=; k<n; k++)
{
if(KMP(s[k], a)== && KMP(s[k], b)==)
break;
} if(k==n)
{
index = i;
i=-, j=;
}
} if(index)
printf("%d\n", index);
else
printf("0\n"); }
return ;
}