【jzoj4910】【子串】【字符串】【kmp】

题目大意

有n个字符串，求编号最大的字符串，它前面有一个串不是它的子串。

解题思路

顺序枚举当前字符串now，维护一个指针表示最前一个不是当前串的子串的串，可以发现如果当前串是后面串的子串，前面的串也一定是后面串的子串，每个串都只考虑一次，所以复杂度是可以的。

code

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define min(a,b) ((a<b)?a:b) #define max(a,b) ((a>b)?a:b) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=500,maxl=2000; int t,n,len[maxn+10],fail[maxl+10]; char s[maxn+10][maxl+10]; bool cmp(int x,int y){ if(len[x]>len[y])swap(x,y); fo(i,2,len[x]){ fail[i]=fail[i-1]; for(;fail[i]&&(s[x][i]!=s[x][fail[i]+1]);fail[i]=fail[fail[i]]); fail[i]+=(s[x][i]==s[x][fail[i]+1]); } int now=0; fo(i,1,len[y]){ for(;now&&(s[y][i]!=s[x][now+1]);now=fail[now]); now+=(s[y][i]==s[x][now+1]); if(now==len[x]) return 1; } return 0; } int main(){ freopen("sub.in","r",stdin); freopen("sub.out","w",stdout); scanf("%d",&t); fo(cas,1,t){ scanf("%d",&n); int ans=-1,now=1; fo(i,1,n){ scanf("%s",s[i]+1);len[i]=strlen(s[i]+1); for(;(now!=i)&&(cmp(now,i));now++); if(now!=i)ans=i; } printf("%d\n",ans); } return 0; }