Problem Description
Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.
For n given strings S 1 ,S 2 ,?,S n , 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 S j is not a substring of S i .
A substring of a string S i is another string that occurs in S i . 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 S 1 ,S 2 ,?,S n , 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 S j is not a substring of S i .
A substring of a string S i is another string that occurs in S i . 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 S 1 ,S 2 ,?,S n .
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 S 1 ,S 2 ,?,S n .
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
2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）
题意：求第i个字符串不是 1—i 个字符串（存在一个匹配不成就行），求 i 的最大值
首先定义一个vis[i][j]数组 用来存放第i个字符串与第j个字符串匹配情况，mapp[i]数组表示第i个字符串是之前字符串的子串
i从1开始 j从i-1开始匹配 ，如果第i个字符串与第j个字符串匹配成功，就更新vis数组，寻找可能不匹配的字符串在此匹配；否则，mapp[i]标记，退出当前循环。
然后从大到小判断第i个字符串与之前的是否匹配
若i==0，则输出-1即可，否则输出i+1
代码如下：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std;const int N=500+5; const int NMAX=2000+5; int vis[N][N],mapp[N]; int next_s[NMAX]; char s[N][NMAX]; void get_next(int next_s[],char s[],int len) {int i=0,j;j=next_s[0]=-1;while(i<len){if(j==-1||s[i]==s[j]){i++,j++;next_s[i]=j;}elsej=next_s[j];} } int kmp(char s[],char t[],int ls,int lt) {int i=0,j=0;int ans=0;while(i<ls){if(j==-1 || s[i]==t[j])i++,j++;elsej=next_s[j];if(j>=lt){ans++;break;}}return ans; } int main() {int t,n;scanf("%d",&t);int count=1;while(t--){memset(vis,0,sizeof(vis));memset(mapp,1,sizeof(mapp));scanf("%d",&n);scanf("%s",s[0]);for(int i=1;i<n;i++){scanf("%s",s[i]);int len_si=strlen(s[i]);for(int j=i-1;j>=0;j--){if(j==i-1){memset(next_s,0,sizeof(next_s));int len_sj=strlen(s[j]);get_next(next_s,s[j],len_sj);int ans=kmp(s[i],s[j],len_si,len_sj);if(ans!=0)//匹配成功{for(int k=0;k<j;k++)vis[i][k]=vis[i][k]|vis[j][k];vis[i][j]=1;}else{mapp[i]=0;break;}}else{if(!vis[i][j]){int len_sj=strlen(s[j]);memset(next_s,0,sizeof(next_s));get_next(next_s,s[j],len_sj);int ans=kmp(s[i],s[j],len_si,len_sj);if(ans!=0)//匹配成功{for(int k=0;k<j;k++)vis[i][k]=vis[i][k]|vis[j][k];vis[i][j]=1;}else{mapp[i]=0;break;}}}}}int i;for(i=n-1;i>=1;i--)if(mapp[i]==0)break;if(i==0)printf("Case #%d: -1\n",count++);elseprintf("Case #%d: %d\n",count++,i+1);}return 0; }