题意：给定n个由小写字母组成的字符串，第i个字符串为a[i]，求最大的j满足存在1<=i<j，a[i]不是a[j]的子串，无解输出-1
T<=50,n<=500,len[i]<=2000
思路：队友写的，抱大腿
判断某个串是否是另一个串的子串可以使用KMP
有一个优化：若a[i-1]是a[i]的子串，则将a[i-1]标记，后面不需要再枚举它
队友的写法是把连续一段缩成了一个
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=;
char s[maxn][maxn<<];
int nxt[maxn][maxn<<];
int len[maxn];
int p[maxn];
void getnext(int x)
{
int i=; int j=;
nxt[x][]=;
int n=len[x];
while(j<=n)
{
if(!i||s[x][i]==s[x][j])
{
i++; j++;
nxt[x][j]=i;
}
else i=nxt[x][i];
}
}
int kmp(int x,int y)
{
int i=; int j=;
int m=len[x];
int n=len[y];
while(j<=m)
{
if(!i||s[y][i]==s[x][j])
{
i++; j++;
if(i>n)
{
return ;
}
}
else i=nxt[y][i];
}
return ;
}
int main()
{
int T;
scanf("%d",&T);
int cas=;
while(T--)
{
int n;
scanf("%d",&n);
memset(s,,sizeof(s));
for(int i=;i<=n;i++)
{
scanf("%s",s[i]+);
len[i]=strlen(s[i]+);
getnext(i);
}
int g=;
int num=;
int r=n;
int l=;;
for(int i=n;i>=;i--)
{
if(!kmp(i,i-))
{
if(num==)
{
l=i;
}
p[++num]=i-;
}
}
printf("Case #%d: ",++cas);
if(!l)
printf("-1\n");
else
{
for(int i=;i<=num;i++)
{
for(int j=r;j>=l;j--)
{
if(!kmp(j,p[i]))
{
l=j;
break;
}
}
if(l==r)
break;
}
printf("%d\n",l);
}
}
}