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".
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
- 找到最大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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include