基于两个串a和b，问a在b中重复了几次。要对KMP进行一些修改，其实只是在模式串匹配完之后，ans++，并且让模式串的j回到原来的位置重来而已。
#include <cstdio> #include <cstring> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define maxN 1000005 int nxt[maxN], n, m, cas, ans; char a[maxN], b[maxN]; void getNxt(char *b, int m, int *nxt) { nxt[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || b[i] == b[j]) ++i, ++j, nxt[i] = j; else j = nxt[j]; } } void kmp(char *a, int n, char *b, int m) { getNxt(b, m, nxt); int i = 0, j = 0; while (i < n) { while (-1 != j && a[i] != b[j]) j = nxt[j]; ++i, ++j; if (j >= m) { ++ans; j = nxt[j]; } } } int main () { // freopen("data.in", "r", stdin); scanf("%d", &cas); while (cas--) { scanf("%s%s", b, a); n = (int)strlen(a), m = (int)strlen(b); ans = 0; kmp(a, n, b, m); printf("%d\n", ans); } return 0; }
poj 2752 Seek the Name, Seek the Fame
给你一个字符串，问前缀和后缀相同的字符串长度可以为多少？
考的是对next数组的理解。假设串为s，长度为L，那么next[L]，即是s的最长前后缀长度，是答案之一，这里设这里的最长前缀为A，最长后缀为B。更短的”前缀-后缀串“必然也是A的前缀和B的后缀的公共部分，又因为A=B，那么问题变成了A的最长公共前后缀问题，如此便可不断回溯回去。
#include <cstdio> #include <cstring> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define maxN 400005 char a[maxN]; int m, ans[maxN], nxt[maxN]; void getNxt(char *b, int m, int *nxt) { nxt[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || b[i] == b[j]) ++i, ++j, nxt[i] = j; else j = nxt[j]; } } int main () { // freopen("data.in", "r", stdin); while (~scanf("%s", a)) { m = (int)strlen(a); getNxt(a, m, nxt); int cnt = 0; int cur = m, j = nxt[cur]; while (j) ans[++cnt] = j, j = nxt[j]; FOR(i, 1, cnt) printf("%d ", ans[cnt - i + 1]); printf("%d\n", m); } return 0; }
问的是一个字符串，其最多能由多少个循环节构成。可以参考这篇说明
#include <cstdio> #include <cstring> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define maxN 1000005 char s[maxN]; int nxt[maxN]; void getNxt(char *b, int m, int *nxt) { nxt[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || b[i] == b[j]) nxt[++i] = ++j; else j = nxt[j]; } } int main () { // freopen("data.in", "r", stdin); while (~scanf("%s", s) && strcmp(s, ".")) { int m = (int)strlen(s); getNxt(s, m, nxt); if (m % (m - nxt[m]) == 0) printf("%d\n", m / (m - nxt[m])); else puts("1"); } return 0; }
问的是最少加入几个字符能使得这个串是循环的。
分几种情况：1，整个串无法被循环， 即nxt[m]=0，此时直接再来一个串接后面才行。
2，本身已经是循环串，此时m%(m-nxt[m])==0，直接输出0即可。
3，前缀是循环串，这个时候找到那个nxt[i]==0 （意味着前面就一个串，不循环），或者是i%(i-nxt[i])==0，此时即[0,i)这个串是循环串，得出最小循环节长度，设为L，答案就是L-后缀长度。
#include <cstdio> #include <cstring> using namespace std; #define maxN 100006 int nxt[maxN], cas, idx; char a[maxN]; void getNxt(char *v, int m) { nxt[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || v[i] == v[j]) nxt[++i] = ++j; else j = nxt[j]; if (nxt[i] == 0 || i % (i - nxt[i]) == 0) idx = i; } } int main () { // freopen("data.in", "r", stdin); scanf("%d", &cas); while (cas--) { scanf("%s", a); int m = (int)strlen(a); getNxt(a, m); if (nxt[m] == 0) { printf("%d\n", m); } else if (m % (m - nxt[m]) == 0) { puts("0"); } else { // 循环节长度 int L = idx - nxt[idx]; int tail = m - idx; printf("%d\n", L - tail); } } return 0; }
hdu 3336 Count the string
问的是所有的前缀，在字符串中一共出现了几次？
假设某个前缀A和后缀B一样，那么B相当于给A贡献了B.length()分数。于是乎问题变成了：问有多少和前缀串相同的后缀串。但是因为如果单反前后缀一样就加分，会重复计算，比如说：
aaauvwaaa，第7和第8个a组成的aa会贡献2分，当加入第9个a成为aaa时，如果你又认为贡献3分，就会重复计算了第7个第8个连成的"aa"的分数。于是：当nxt[i]+1!=nxt[i+1]时，表示到i的后缀和到i+1的后缀是不一样的，才进行加分。
#include <cstdio> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define maxN 200005 int nxt[maxN], cas, n; char a[maxN]; void getNxt(char *v, int m) { nxt[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || v[i] == v[j]) nxt[++i] = ++j; else j = nxt[j]; } } int main () { // freopen("data.in", "r", stdin); scanf("%d", &cas); while (cas--) { scanf("%d %s", &n, a); getNxt(a, n); int ans = (n + nxt[n]) % 10007; FOR(i, 0, n - 1) { if (nxt[i] && nxt[i] + 1 != nxt[i + 1]) ans = (ans + nxt[i]) % 10007; } printf("%d\n", ans); } return 0; }
原文：https://www.cnblogs.com/Rosebud/p/9850122.html