数据结构-KMP字符串模式匹配算法实现 （C++代码）

        

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 2130;
int perfix[SIZE];

void getPerfix(string patt) {
	for (int sta(0), end(1); end < patt.size();) {
		if (patt[sta] == patt[end])
			perfix[end++] = 1 + sta++;
		else if (!sta)
			perfix[end++] = 0;
		else
			sta = perfix[sta - 1];
	}
}

void KMP(string text, string patt) {
	getPerfix(patt); int Indst(0), Indnd(0);
	while (Indst < text.size() && Indnd < patt.size()) {
		if (text[Indst] == patt[Indnd])
			Indst++, Indnd++;
		else if (!Indnd)
			Indst++;
		else
			Indnd = perfix[Indnd - 1];
	}
	cout << (Indnd == patt.size() ? Indst - patt.size() + 1 : 0) << endl;
	return;
}

int main() {
	ios::sync_with_stdio(false);
	string text, patt; 
	while (cin >> text >> patt) {
		KMP(text, patt); text.clear(); patt.clear();
	}
}