Bazinga

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

abc

zabc

abcd

zabcd

you

lovinyou

aboutlovinyou

allaboutlovinyou

def

abcd

abcde

abcdef

ccc

Sample Output

Case #1: 4

Case #2: -1

Case #3: 4

Case #4: 3

题意：给出n个串，求出最大的i使得有一个j（1<=j<i）不是i的子串。

思路：比赛的时候由于没剩下多少时间，写的太暴力了TLE，后面自己写了一个，发现别人写的也很暴力，还有用strstr过的，速度普遍比用KMP的快。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define M 2010
 6 #define N 510
 7 int nxt[M];
 8 char s[N][M];
 9 
10 void make_next(char *s)
11 {
12     memset(nxt, 0, sizeof(nxt));
13     int j = -1, i = 0;
14     nxt[0] = -1;
15     int len = strlen(s);
16     while(i < len) {
17         if(j == -1 || s[i] == s[j]) {
18             i++; j++;
19             nxt[i] = j;
20         } else {
21             j = nxt[j];
22         }
23     }
24 }
25 
26 int kmp(char *s, char *str)
27 {
28     make_next(s);
29     int l = strlen(s), len = strlen(str);
30     int i = 0, j = 0;
31     while(i < len && j < l) {
32         if(j == -1 || str[i] == s[j]) {
33             i++; j++;
34             if(j >= l) return true;
35         } else {
36             j = nxt[j];
37         }
38     }
39     return false;
40 }
41 
42 int main()
43 {
44     int t;
45     int cas = 0;
46     scanf("%d", &t);
47     while(t--) {
48         int n;
49         scanf("%d", &n);
50         for(int i = 1; i <= n; i++)
51             scanf("%s", s[i]);
52 
53         int tmp = -100;
54         for(int i = n; i > 1; i--){
55             if(!kmp(s[i-1], s[i])) {
56                  tmp = i;
57                  break;
58             }
59         }
60 //        printf("TMP : %d
", tmp);
61         int ans = tmp;
62         for(int i = tmp - 1; i > 0; i--) {
63             while(!kmp(s[i], s[ans+1]) && ans < n) {
64                 ans++;
65             }
66         }
67 
68         printf("Case #%d: ", ++cas);
69         if(tmp != -100)
70             printf("%d
", ans);
71         else
72             printf("-1
");
73     }
74     return 0;
75 }