题目描述 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) such that Sj is not a substring of Si . For example, “izh” is a substring of “ruizhang”,and “zrui” is not a substring of “ruizhang”.
输入 The first line contains an integer t (1 ≤ t ≤ 100) 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, output the largest label you get. If it does not exist, output −1.
样例输入 3 4 aa ab aba aaba 5 a ba acba abaaacaabaa dabadaacasabaza 3 a ba ccc
样例输出 Case #1: 2 Case #2: -1 Case #3: 3
思路 这题与hdu上的题不同，这题要判断的不是字串而是子序列，因此不能用strstr函数，需要手写一个check函数，每次检测后，若出现字符串j为字符串i的子串，则该字符串j在下次判断时可略去，以避免重复比较
代码实现
#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; const int N=505; typedef long long ll; int n; char s[N][2005]; bool vis[N]; bool check(int a,int b) { int p=0; int al=strlen(s[a]),bl=strlen(s[b]); if(al>bl) return false; for(register int i=0;i<bl && p<al;++i) { if(al-p>bl-i) return false; if(s[a][p]==s[b][i]) p++; } if(p==al) return true; return false; } int main() { int T; scanf("%d",&T); for(int id=1;id<=T;id++) { int ans=-1; scanf("%d",&n); for(int i=1;i<=n;i++) { vis[i]=false; scanf("%s",s[i]); for(int j=1;j<i;j++) { if(vis[j]) continue; if(!check(j,i)) { ans=i; break; } vis[j]=true; } } printf("Case #%d: %d\n",id,ans); } return 0; }