题意：
给你n（1<=n<=500)个长度最多为2000的字符串，现在让你找出最大的i使得存在j(1<=j
思路：
直接暴力比较每个字符串是不是当前考虑的这个字符串的子串，然后加上一个优化就是从最近的一个字符串开始，这个字符串满足其前面的字符串都是当前串的子串，然后还有就是如果待比较的字符串长度明显不满足直接返回false。然后判断是不斯匹配我写了一个KMP,不知道不用KMP能不能过
代码：
#include<cstring>
#include<cctype>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=
500+
10;
const int maxlen=
2000+
10;
char str[maxn][maxlen];
int kase=
0;
void solve();
bool check(
char * s,
char * t);
int main()
{
int T;
kase=
0;
scanf(
"%d",&T);
while(T--){
kase++;
solve();
}
return 0;
}
void solve()
{
int n;
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++){
scanf(
"%s",str[i]);
}
int ans=-
1;
int pre=
1;
bool flag;
for(
int i=
2;i<=n;i++){
flag=
true;
for(
int j=pre;j<i;j++){
if(!check(str[j],str[i])){
ans=max(ans,i);
flag=
false;
break;
}
}
if(flag){
pre=max(pre,i);
}
}
printf(
"Case #%d: %d\n",kase,ans);
}
void getfail(
char * s,
int n,
int * f);
bool check(
char * s,
char * t)
{
int n=
strlen(s),m=
strlen(t);
if(n>m)
return false;
static int fail[maxlen];
getfail(s,n,fail);
int j=
0;
for(
int i=
0;i<m;i++){
while(j&&s[j]!=t[i]) j=fail[j];
if(s[j]==t[i]) j++;
if(j==n)
return true;
}
return false;
}
void getfail(
char * s,
int n,
int * f)
{
f[
0]=
0;
f[
1]=
0;
int j=
0;
for(
int i=
1;i<n;i++){
j=f[i];
while(j&&s[j]!=s[i]) j=f[j];
if(s[j]==s[i]) j++;
f[i+
1]=j;
}
}
