HDU 5510 题解

题意：对于n个字符串，找到最大的i，满足条件：S₁，S₂，……，S_i-1中至少存在一个字符串不是S_i的子串。

1<=N<=500;字符串长度不超过2000.共1~50组数据，1000MS

算法/思路：

KMP即可，先从大到小判断KMP(S_i，S_i+1)，若连续为真，说明S_i为S_i+1，S_i+2，……，S_n的子串；若到某个i为假，说明S_i+1满足条件(但未必最大)。注意此时S_i+1为S_i+2，……，S_n的子串，故S_i+1的子串必定为S_i+2，……，S_n的子串。

令bound=i+1如果kmp(i,bound)不成立，那么bound满足条件，++bound，否则--i（因为当前S_i是bound及以后字符串的子串，没有判断价值），继续进行判断，直到i=1或者bound=n+1，答案为bound-1，复杂度为O(n*length)。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=3000;

char s[600][maxn];
int next1[maxn][maxn];

int t,n,ans,bound;

void ms(int v){
    int n=strlen(s[v]);int i=0,j=-1;next1[v][0]=-1;
    while (i!=n){
        if (j!=-1 && s[v][i]!=s[v][j]) j=next1[v][j];
        ++i;++j;
        if (s[v][i]==s[v][j]) next1[v][i]=next1[v][j];else next1[v][i]=j;
    }
}

int kmp(int a,int b){
    int n=strlen(s[a]),m=strlen(s[b]);
    int i=0,j=0;
    while (i<m){
        if (s[b][i]==s[a][j]){
            ++i;++j;
            if (j==n) return (i-n+1);
        }    else if (next1[a][j]!=-1) j=next1[a][j];
                    else {j=0;++i;}
    }
    return -1;
}

int main(){
    cin>>t;
    for (int q=1;q<=t;++q){
        cin>>n;
        for (int i=1;i<=n;++i){
            scanf("%s",&s[i]);
            ms(i);
        }
        int i;
        //for (int i=1;i<=n;++i)
            //for (int j=i+1;j<=n;++j) cout<<kmp(i,j)<<endl;
        //cout<<kmp(3,4)<<"asd "<<endl;
        for (i=n-1;i>=1 && kmp(i,i+1)!=-1;--i);
        if (i==0) ans=-1;else{
            bound=i+1;
            for (;i>=1 && bound<=n;--i){
                while (bound<=n && kmp(i,bound)==-1) ++bound;    
            }
            ans=bound-1;
        }
        printf("Case #%d: %d
",q,ans);
    }
    return 0;
}

相关推荐