Bazinga
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 214 Accepted Submission(s): 89
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.
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.
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
【题意】：
n个字符串，找出最大的i，使得存在j 满足j<i 且Sj不是Si的字串。
【解题思路】：
看着是个水题本想直接上，看到一片TLE吓得上了个KMP的板。。。
交了一发还是TLE，已经不想做了。。
在某blog的指点下，先判断相邻两个串是否存在字串关系，若Si是Sj的字串，则i和j只需要kmp()一次即可~
减少kmp()次数后800ms过了，，感觉还是不够优美
搜了一下发现有各种做法，Hash、dp......
有空再改，挖坑待填~~
(代码写得丑==)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define eps 1e-8
#define zero(x)(((x)>0?(x):-(x))<eps)
#define PI acos(-1.0)
#define LL long long
#define maxn 2200
#define IN freopen("in.txt","r",stdin);
using namespace std; char Str[][];
/*KMP--字符串匹配--单一模版串*/
//char str[maxn],p[maxn];/*p is template string*/
int f[maxn],cnt;//when failed,get to f[i];
void getf(char *p)
{
memset(f,,sizeof(f));
int len=strlen(p); /* only cal once, or TLE */
for(int i=;i<len;i++)
{
int j=f[i];
while(j&&p[i]!=p[j]) j=f[j];
f[i+]=(p[i]==p[j]? j+:);
}
}
int kmp(char *str,char *p) /*O(len1+len2)*/
{
getf(p);
cnt=;
int len1=strlen(str),len2=strlen(p); /* only cal once, or TLE*/
for(int i=,j=;i<len1;i++)
{
while(j&&str[i]!=p[j]) j=f[j];
if(str[i]==p[j]) j++;
if(j==len2) cnt++;/*Match success*/
if(cnt!=) break;
}
return cnt;
} int main(int argc, char const *argv[])
{
//IN; int t,ca=;scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%s",Str[i]); int flag[maxn]={};
for(int i=;i<n;i++)
if(kmp(Str[i+],Str[i])!=) flag[i]=; for(int i=n;i>=;i--){
for(int j=;j<i;j++){
if(flag[j]) continue;
kmp(Str[i],Str[j]);
if(cnt==){
printf("Case #%d: %d\n",ca++,i);goto s;
}
}
} printf("Case #%d: -1\n",ca++);
s:continue;
} return ;
}