You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
1.1 KiB
C++
47 lines
1.1 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
using namespace std;
|
|
const int N=2050;
|
|
char str[550][N];
|
|
int next[N];
|
|
int kmp(char*s,char*p)
|
|
{
|
|
int ls=strlen(s),lp=strlen(p);
|
|
next[0]=-1;
|
|
for (int i = 0, j = -1; i <lp; next[++i] = ++j)
|
|
while (~j && p[i] != p[j])
|
|
j = next[j];
|
|
for (int i = 0, j = 0; i < ls&&j<lp; )
|
|
{
|
|
while (~j && s[i] != p[j])
|
|
j=next[j];
|
|
i++,j++;
|
|
if (j == lp)
|
|
return i - j;
|
|
}
|
|
return -1;
|
|
}
|
|
bool flags[N];
|
|
int main()
|
|
{
|
|
int T,n;
|
|
scanf("%d",&T);
|
|
for(int t=1; t<=T; t++)
|
|
{
|
|
memset(flags,0,sizeof(flags));
|
|
scanf("%d",&n);
|
|
for(int i=0; i<n; i++)
|
|
scanf("%s",str[i]);
|
|
for(int i=1; i<n; i++)
|
|
if(kmp(str[i],str[i-1])!=-1)
|
|
flags[i-1]=true;
|
|
int ans=-1;
|
|
for(int i=n-1; i&&ans==-1; i--)
|
|
for(int j=0; j<i&&ans==-1; j++)
|
|
if(!flags[j]&&kmp(str[i],str[j])==-1)
|
|
ans=i+1;
|
|
printf("Case #%d: %d\n",t,ans);
|
|
}
|
|
return 0;
|
|
}
|