kmp算法

#include<cstdio>
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
static int next_table[N];

void nexttable(string s, int len) {
	int p = 0, i = 1;
	next_table[0] = 0;
	while (i < len) {
		if (s[i] == s[p]) {
			p++;
			next_table[i] = p;
			i++;
		}
		else {
			if (p != 0) {
				p = next_table[p-1];
			}
			else {
				next_table[i] = p;
				i++;
			}
		}
	}

	for (int i = len - 1; i > 0; i--) next_table[i] = next_table[i - 1];
	next_table[0] = -1;

}

int kmp(string bigs, string s, int len) {
	int count = 0;
	int m = bigs.length();
	int i = 0, j = 0;
	while (j < m) {
		if (i == len - 1 && s[i] == bigs[j]) {
			count++;
			i = next_table[i];
		}

		if (s[i] == bigs[j]) {
			i++; j++;
		}
		else {
			if (next_table[i] == -1) {
				j++;
			}
			else i = next_table[i];

		}
	}
	return count;

}

int main() {
	string bigs, s;
	cin >> bigs >> s;
	int len = s.length();
	nexttable(s, len);

	cout << kmp(bigs, s, len);
	return 0;
}