Bazinga
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5056 Accepted Submission(s): 1596
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
- 找到最大ID字符串i使得存在j<i的字符串不是i的子串
- 首先考虑如果从l到r串都满足都是r的子串，那么k>r串只需要检测r串即可
- 如果自l串开始到l+k串都是存在小于l的串不是当前串子串，那么对于l+k+1串就要检测l-1串和l到l+k串
- 算法出来了，就是记录当前最大id使得此id之前全是id串的子串，然后检测串的范围就是这个id到当前ID的前一位
- 如果用这样的算法，用c的strstr即可，用kmp可以减少一半时间
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <climits> 7 #include <cmath> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL ; 15 typedef unsigned long long ULL ; 16 const int maxn = 1e5 + 10 ; 17 const int inf = 0x3f3f3f3f ; 18 const int npos = -1 ; 19 const int mod = 1e9 + 7 ; 20 const int mxx = 100 + 5 ; 21 const double eps = 1e-6 ; 22 const double PI = acos(-1.0) ; 23 24 int T, n, use[maxn], mx, ans; 25 char s[505][2005]; 26 std::vector<int> v; 27 int main(){ 28 // freopen("in.txt","r",stdin); 29 // freopen("out.txt","w",stdout); 30 while(~scanf("%d",&T)){ 31 for(int kase=1;kase<=T;kase++){ 32 ans=-1; 33 scanf("%d",&n); 34 mx=1; 35 use[1]=0; 36 v.clear(); 37 scanf("%s",s[1]); 38 for(int i=2;i<=n;i++){ 39 scanf("%s",s[i]); 40 int flag=1; 41 if(strstr(s[i],s[mx])==NULL) 42 flag=0; 43 if(flag&&use[i-1]){ 44 for(int j=v.size()-1;j>=0 && flag;j--){ 45 if(strstr(s[i],s[v[j]])==NULL) 46 flag=0; 47 } 48 } 49 if(flag){ 50 mx=i; use[i]=0; v.clear(); 51 }else{ 52 ans=i; use[i]=1; v.push_back(i); 53 } 54 } 55 56 printf("Case #%d: %dn",kase,ans); 57 } 58 } 59 return 0; 60 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
