HDU 5510

题目大意是给定n个字符串，对于任意一个字符串i (1 <= i <= n) ，问是否存在一个最大的字符串下标i使得存在一个字符串j (1 <= j < i )     不是i的字串，不是则输出-1     思路            kmp     如果直接用kmp进行暴力显然也会超时，我们可以动态维护一个最大值r，对于每一个字符串 i 如果字符串 i 是字符串 j 的子串，则     直接扫描下一个字符串，否则则更新r，对于每一个字符串 i 要扫描的 j 我们直接从r的下一个开始，因为对于任意字符串j<=r，再对这些字符串     进行判断肯定是多余的。 #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <map> using namespace std; const int maxn = 500 + 10; int n; char s[maxn][maxn * 4]; int len[maxn]; int nxt[maxn * 4]; void kmp_pre(int id){ int i, j; j = nxt[0] = -1; i = 0; while(i < len[id]){ while(-1 != j && s[id][i] != s[id][j]) j = nxt[j]; nxt[++i]=++j; } } bool kmp(int p, int t){ int i, j; kmp_pre(p); i = j = 0; while(i < len[t]){ while(-1!=j && s[t][i] != s[p][j]) j = nxt[j]; i++; j++; if(j >= len[p]){ return true; } } return false; } int solve(){ int r = -2; for(int i = 0; i < n; ++i){ for(int j = max(i + 1, r); j < n; ++j){ if(kmp(i, j)) break; r = j; } } return r + 1; } int main() { int T; scanf("%d", &T); int kase = 0; while(T --){ scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%s", s[i]); len[i] = strlen(s[i]); } printf("Case #%d: %d\n", ++kase, solve()); } return 0; }