Bazinga
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4518 Accepted Submission(s): 1442
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".
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
Sample Output
Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3
Source
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w",stdout);
#define INFLL 0x3f3f3f3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
typedef pair<double, double> PII;
const int MX = 2000 + 5;
const int MX2 = 500 + 5;
/*
void GetNext() {
Next[0] = 0;
for(int i = 1; i < n; i++) {
int j = Next[i - 1];
while(j && S[i] != S[j]) j = Next[j - 1];
Next[i] = S[i] == S[j] ? j + 1 : 0;
}
}
*/
int Next[MX], n;
int KMP(char *A, char *B) {
int m = strlen(A), n = strlen(B);
Next[0] = 0;
for(int i = 1; i < n; i++) {
int k = Next[i - 1];
while(B[i] != B[k] && k) k = Next[k - 1];
Next[i] = B[i] == B[k] ? k + 1 : 0;
}
int ans = 0, j = 0;
for(int i = 0; i < m; i++) {
while(A[i] != B[j] && j) j = Next[j - 1];
if(A[i] == B[j]) j++;
if(j == n) ans++;
}
return ans;
}
char ch[MX2][MX];
bool vis[MX2];
int main() {
//FIN
int T;
int cnt = 1;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) scanf("%s", ch[i]);
for(int i = 2; i <= n ;i++)
if(KMP(ch[i], ch[i-1])) vis[i-1] = 1;
int flag = 0;
for(int i = n; i >= 1; i--) {
for(int j = 1; j < i; j++) {
if(!vis[j])
if(KMP(ch[i], ch[j]) == 0) {
flag = 1;
printf("Case #%d: %d
", cnt++, i);
break;
}
}
if(flag) break;
}
if(!flag) printf("Case #%d: -1
", cnt++);
}
return 0;
}