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
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
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
Case #2: -1
Case #3: 4
Case #4: 3
Source
Recommend
/*
用两个指针模拟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 ;
}