题解 | #String Matching#

//土尔逊Torson 编写于2023/4/22
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stdlib.h>

using namespace std;

const int MAXM = 10000;

int nextTable[MAXM];

void GetNextTable(string pattern) {
	int m = pattern.size();
	int j = 0;
	nextTable[j] = -1;
	int i = nextTable[j];
	while (j < m) {
		if (i == -1 || pattern[j] == pattern[i]) {
			i++;
			j++;
			nextTable[j] = i;
		}
		else {
			i = nextTable[i];
		}
	}
	return;
}

int KMP(string text, string pattern) {
	GetNextTable(pattern);
	int n = text.size();
	int m = pattern.size();
	int i = 0;
	int j = 0;
	int number = 0;
	while (i < n) {
		if (j == -1 || text[i] == pattern[j]) {
			i++;
			j++;
		}
		else {
			j = nextTable[j];
		}
		if (j == m) {
			number++;
			j = nextTable[j];
		}
	}
	return number;
}

int main() {
	string line;
	while (getline(cin,line)) {
		string pattern, text;
		int g = line.find(' ');
		int u = line.find('\0');
		//printf("%d %d\n", g, u);
		text = line.substr(0, g);
		pattern = line.substr(g + 1,u-g);
		//printf("%s %s\n", text.c_str(), pattern.c_str());
		printf("%d\n", KMP(text, pattern));
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")