HDU5510Bazinga 【KMP】

Bazinga Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3716 Accepted Submission(s): 1207 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 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亚洲区沈阳站-重现赛（感谢东北大学）

考虑kmp比较字符串 然后直接暴力的话 O(t∗n2∗2000) 显然会T 考虑S1是S2的子串 Sn与S1~Sn-1比较时 显然如果比较了S2,S1就没必要再比较了 S2是Sn的子串,S1也肯定是,S2不是Sn子串，ans=max(n,ans)

#include<iostream> #include<cstdlib> #include<cstdio> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<ctime> #include <string.h> #include<math.h> using namespace std; #define ll long long #define pii pair<int,int> const int inf=1e9+7; const int N = 2e3+5; int Next[505][N]; char str[505][N]; bool flag[505]; void get_Nextval(char *P, int *next) { int j = 0; int k = -1; next[0] = -1; int slen = strlen(P); while( j < slen ) { if( -1 == k || P[j] == P[k] ) { ++k; ++j; if( P[j] != P[k] ) { next[j] = k; } else { next[j] = next[k]; } } else { k = next[k]; } } } int index_KMP(char *S, char *P,int*next) { int i = 0; int j = 0; while( i < strlen(S) && j < strlen(P) || -1 == j ) { if( -1 == j || S[i] == P[j] ) { ++i; ++j; } else { j = next[j]; //移动的位数 } } if( j == strlen(P) ) //匹配成功 { return i - j + 1; } else return -1; } int slove(int n){ for(int i=1;i<=n;++i){ get_Nextval(str[i],Next[i]); } int ans=-1; fill(flag,flag+n+1,false);//是后面的串的子串? for(int i=2;i<=n;++i){ for(int j=i-1;j>=1;--j){ if(flag[j]){ continue; } if(-1==index_KMP(str[i],str[j],Next[j])){ ans=max(i,ans); break; } else{ flag[j]=true; } } } return ans; } int main(int argc, char *argv[]) { //freopen("/home/lu/Documents/r.txt","r",stdin); int T; scanf("%d",&T); for(int t=1;t<=T;++t){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s",str[i]); } printf("Case #%d: %d\n",t,slove(n)); } return 0; }