主要是理解getnext的函数，它是由KMP及递推的思想得出的。
简单的应用 HDUOJ 1711 Number Sequence
int s[maxn], t[maxm], _next[maxn], n, m; void get_next(int *t, int *_next) { int i = 1, j = 0; _next[1] = 0; while (i < m) { if (j == 0 || t[i] == t[j]) { ++i, ++j; if(t[i] != t[j])_next[i] = j; else _next[i] = _next[j]; } else j = _next[j]; } } int KMP(int *s, int *t, int *_next) { get_next(t, _next); int i = 1, j = 1; while (i <= n && j <= m) { if (j == 0 || s[i] == t[j]) ++i, ++j; else j = _next[j]; } if (j > m) return i - m; return -1; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &s[i]); for (int i = 1; i <= m; ++i) scanf("%d", &t[i]); printf("%d\n", KMP(s, t, _next)); } return 0; }get_next的i手残打成了j，20000次之后竟然自己跳出了循环。。不是应该死循环么。。。。 HDUOJ 1686 Oulipo char s[maxn], t[maxm]; int _next[maxm], slen, tlen; void get_next() { int i = 0, j = -1; _next[0] = -1; while (i < tlen) { if (j == -1 || t[i] == t[j]) { ++i, ++j; if (t[i] == t[j]) _next[i] = _next[j]; else _next[i] = j; } else j = _next[j]; } } int KMP() { get_next(); int i = 0, j = 0, ret = 0; while (1) { while (i < slen && j < tlen) { if (j == -1 || s[i] == t[j]) ++i, ++j; else j = _next[j]; } if(j >= tlen) j = _next[j], ret++; if (i >= slen) break; } return ret; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%s%s", t, s); tlen = strlen(t); slen = strlen(s); printf("%d\n", KMP()); } return 0; }我渐渐感觉有些题顺其自然就能写出来了。 HDUOJ 3746 Cyclic Nacklace 思路: next[len]表示已有的和前缀相同的长度，len - next[len]表示最小循环节。 char s[maxn]; int _next[maxn]; int main() { int T; scanf("%d", &T); while (T--) { scanf("%s", s); int len = strlen(s); int i = 0, j = -1; _next[0] = -1; while (i < len) { if (j == -1 || s[i] == s[j]) ++i, ++j, _next[i] = j; else j = _next[j]; } int ans = 0; if (_next[len] != 0 && len % (len - _next[len]) == 0) ans = 0; else ans = len - _next[len] - len % (len - _next[len]); printf("%d\n", ans); } return 0; }