HDU 5510 Bazinga（KMP||strstr神器+些许优化）_综合

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

For nn given strings S1,S2,?,SnS1,S2,?,Sn, labelled from 11 to nn, you should find the largest i (1≤i≤n)i (1≤i≤n) such that there exists an integer j (1≤j<i)j (1≤j<i) and SjSj is not a substring of SiSi.

A substring of a string SiSi is another string that occurs in SiSi. 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)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)n (1≤n≤500) and in the following nn lines list are the strings S1,S2,?,SnS1,S2,?,Sn.
All strings are given in lower-case letters and strings are no longer than 20002000letters.

Output

For each test case, output the largest label you get. If it does not exist, output ?1?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

题解：

题意：

让你从一堆有编号的串中找出最后面的一个i，使得在[1，i-1]中可以找到一个串s[j]不是s[i]的子串

思路：

直接搞看上去都是要炸的，所以要做一些优化，比如如果s[j-1]是s[j]的子串，那么如果s[j-1]不是s[i]的子串，那么s[j]也不是，反之如果s[j]是s[i]的子串，那么s[j-1]也一定是s[i]的子串，这样想预处理扫一遍数组，将前后有这种包含关系的标记一下就好了，然后从后面往前暴力扫

代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long
#define INF 1008611111
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
char s[505][2005];
int vis[505];
int main()
{int i,j,k,test,q,n,d;scanf("%d",&test);for(q=1;q<=test;q++){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%s",s[i]);vis[i]=0;}printf("Case #%d: ",q);d=-1;for(i=2;i<=n;i++){if(strstr(s[i],s[i-1])!=NULL)vis[i-1]=1;}for(i=n;i>=1;i--){for(j=1;j<i;j++){if(vis[j])continue;if(strstr(s[i],s[j])==NULL){d=i;goto loop;}}}loop:;printf("%d\n",d);}return 0;
}