题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5510
题意:至多50组数据，每组数据至多500个字符串，每个字符串的长度最长为2000.问最大的下标(从1开始)j,使得存在i < j使得s[i]不是s[j]的子串；
思路:KMP很容易想到，因为Trie是处理前缀串的，不能处理子串。在KMP中，还要优化下，就是父串可以代表子串，并且直接递推处理(用尺取法，每次处理没有父串的串)即可；
#include<bits/stdc++.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair typedef __int64 ll; typedef unsigned int uint; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } int T,kase = 1,i,j,k,n,m,ans; char s[505][2020]; int f[2020]; void getfail(char *p) { f[0] = f[1] = 0; int n = strlen(p); for(int i = 1;i < n;i++){ int j = f[i]; while(j && p[i] != p[j]) j = f[j];//之前写的KMP竟然写成了if()..竟然过了 f[i+1] = (p[i] == p[j] ?j+1:0);// ｉ＋１会递推到第ｎ位 } } bool Find(char *p,char *T) { getfail(p); int j = 0,n = strlen(T),m = strlen(p); for(int i = 0;i < n;i++){ while(j && T[i] != p[j]) j = f[j]; if(T[i] == p[j]) j++; if(j == m) return true; } return false; } int main() { //freopen("data.txt","r",stdin); //freopen("out.txt","w",stdout); read1(T); while(T--){ MS0(Next); read1(n); rep1(i,1,n) scanf("%s",s[i]); int ans = -1; for(int l = 1,r = 2;r <= n;r++){ while(l < r){ //用尺取法之后就不需要再进行前驱表示父子关系了 if(Find(s[l],s[r])) l++; else{ ans = r;break;} } } printf("Case #%d: %d ",kase++,ans); } return 0; }