「Note」KMP

KMP算法模板

const int MAXN = 1e6 + 5;

char a[MAXN], b[MAXN];
int nxt[MAXN], f[MAXN], ans;

void KMP(char* a, char* b) {
	int n = strlen(a + 1), m = strlen(b + 1);
	nxt[1] = 0;
	for (int i = 2, j = 0; i <= n; i++) {
		while (j > 0 && a[i] != a[j + 1]) j = nxt[j];
		if (a[i] == a[j + 1]) j++;
		nxt[i] = j;
	}
	for (int i = 1, j = 0; i <= m; i++) {
		while (j > 0 && (j == n || b[i] != a[j + 1])) j = nxt[j];
		if (b[i] == a[j + 1]) j++;
		f[i] = j;
		if (f[i] == n) {
			ans++;
		}
	}
	printf ("%d\n", ans);
}