HDU5510(Bazinga)

链接：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;
}