链接：https://vjudge.net/problem/HDU-5510
思路：首先暴力匹配复杂度肯定不能接受，我们考虑如果对任意两个串用kmp可以把单词匹配复杂度降到O(len)，这样整个复杂度就是O(tnn*len)，这样还是会超时，我们考虑对于前面一个串如果是后面一个串的字串，那么我们只用跟后面那个串进行比较，这样一来因为只用求最大的下标位置，所以我们先预处理所有相邻串的关系，然后相邻串进行暴力kmp即可，这样可以减少大量的不必要运算，从而计算出结果。
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n,cnt;
char str[510][2010];
int flag[510];
int f[2010];
void getfail(char *P){
int m = strlen(P);
f[0] = 0;
f[1] = 0;
for(int i=1;i<m;i++){
int j = f[i];
while(j&&P[i]!=P[j])j = f[j];
f[i+1] = P[i] == P[j]?j+1:0;
}
}
bool find(char *T,char *P){
int n = strlen(T);
int m = strlen(P);
cnt = 0;
memset(f,0,sizeof(f));
getfail(P);
int j = 0;
for(int i=0;i<n;i++){
while(j&&P[j]!=T[i])j = f[j];
if(P[j]==T[i])j++;
if(j==m)cnt++;
if(cnt!=0)break;
}
return cnt;
}
int main(){
int kase = 0;
scanf("%d",&t);
while(t--){
memset(flag,0,sizeof(flag));
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%s",str[i]);
for(int i=0;i<n-1;i++){
if(find(str[i+1],str[i])!=0)//预处理所有的相邻串
flag[i] = 1;
}
int fff = 0;
for(int i=n-1;i>=0;i--){
int ff = 0;
for(int j=0;j<i;j++){
if(flag[j])continue;
find(str[i],str[j]);
if(cnt==0){
printf("Case #%d: %d\n",++kase,i+1);
ff = 1;
break;
}
}
if(ff){
fff = 1;
break;
}
}
if(!fff)printf("Case #%d: %d\n",++kase,-1);
}
return 0;
}
