【JZOJ4910】子串

Description

给出n个字符串 Si ，求最大的 j ，使得存在一个i<j，且 Si 不是 Sj 的子串。输出最大的 j 。

有T组数据。

Solution

这题有许多方法（其中AC自动机会超时）。

我们可以开一个类似栈的东西，存储相邻匹配的字符串。

举个例子：a1,a2,...,atop是一个栈，其中 sa2 是 sa1 的子串，以此类推。

于是我们倒着做： 假设现在栈顶为 atop ，我们当前枚举到字符串 Si ，我们看它是不是 Stop 的子串，如果不是，那么更新答案，这时 Stop 就可以删去了（因为这个字符串已经存在不是它的子串的字符串）。

Code

#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define ll long long #define N 510 #define S 2010 using namespace std; int nx[N][S]; char s[N][S]; int d[N]; int l[N]; void get(int z) { int j=0; fo(i,2,l[z]) { while(j && s[z][j+1]!=s[z][i]) j=nx[z][j]; if(s[z][j+1]==s[z][i]) j++; nx[z][i]=j; } } bool kmp(int x,int y) { if(l[x]>l[y]) return false; int j=0; fo(i,1,l[y]) { while(j && s[x][j+1]!=s[y][i]) j=nx[x][j]; if(s[x][j+1]==s[y][i]) j++; if(j==l[x]) return true; } return false; } int main() { freopen("sub3.in","r",stdin); freopen("sub.out","w",stdout); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); fo(i,1,n) { scanf("%s",s[i]+1); l[i]=strlen(s[i]+1); get(i); } d[0]=1; d[1]=n; int ans=-1; fd(i,n-1,1) { while(!kmp(i,d[d[0]]) && d[0]) { ans=max(ans,d[d[0]]); d[0]--; } d[++d[0]]=i; } printf("%d\n",ans); memset(nx,0,sizeof(nx)); } }