2015ACM/ICPC亚洲区沈阳站 B-Bazinga

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Bazinga

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3509 Accepted Submission(s): 1122

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

For n

given strings S1,S2,⋯,Sn

, labelled from 1

to n

, you should find the largest i (1≤i≤n)

such that there exists an integer j (1≤j<i)

and Sj

is not a substring of Si

A substring of a string Si

is another string that occurs in Si

. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

Input

The first line contains an integer t (1≤t≤50)

which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500)

and in the following n

lines list are the strings S1,S2,⋯,Sn

.
All strings are given in lower-case letters and strings are no longer than 2000

letters.

Output

For each test case, output the largest label you get. If it does not exist, output −1

Sample Input

4
5
ab
abc
zabc
abcd
zabcd
4
you
lovinyou
aboutlovinyou
allaboutlovinyou
5
de
def
abcd
abcde
abcdef
3
a
ba
ccc

Sample Output

Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3

Source

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

Recommend

wange2014 | We have carefully selected several similar problems for you: 5960 5959 5958 5957 5956

/*
用两个指针模拟kmp，暴力
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define N 505
using namespace std;
///
int t,n;
int ne[];
void getnext(char *s2)
{
int i=,j=-,l=strlen(s2);
ne[]=-;
while(i<l)
{
if(j==-||s2[i]==s2[j])
{
i++;j++;
if(s2[i]==s2[j])
ne[i]=ne[j];
else
ne[i]=j;
}
else
j=ne[j];
}
}
int kmp(char *s,char *s2)
{
memset(ne,,sizeof(ne));
getnext(s2);
int i=,j=,k=,len=strlen(s),l=strlen(s2);
while(i<len)
{
if(j==-||s[i]==s2[j])
i++,j++;
else
j=ne[j];
if(j==l)
k++,j=ne[j];
}
return k;
}
char s[N][]={""};
bool vis[N],f;
int main()
{
//freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);
scanf("%d",&t);
int Case=;
while(t--)
{
memset(vis,true,sizeof vis);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%s",s[i]);
printf("Case #%d: ",Case++);
for(int i=;i<=n;i++)
if(kmp(s[i],s[i-])>)
vis[i-]=false;
int f=;
for(int i=n;i>=&&!f;i--)
for(int j=;j<i&&!f;j++)
if(vis[j])
if(kmp(s[i],s[j])==)
{
printf("%d\n",i);
f=true;
}
if(!f)
puts("-1");
}
return ;
}