[알고리즘] KMP 알고리즘 O(N+M)

• 문자열 검색 알고리즘. for문 한번만 돌기 때문에 좋다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> makeTable(string pattern) {
	int j = 0;
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	for (int i = 1; i < patternSize; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}
void KMP(string parent, string pattern) {
	vector<int> table = makeTable(pattern);
	int j = 0;
	int parentSize = parent.size();
	int patternSize = pattern.size();
	for (int i = 1; i < parentSize; i++) {
		while (j > 0 && parent[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (parent[i] == pattern[j]) {
			if (j == patternSize - 1) {
				cout << i - patternSize + 2 << " 번째에서 발견!" << endl;
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}
int main() {
	string parent = "abaabaaaabaabcca";
	string pattern = "aaab";

	KMP(parent, pattern);

	return 0;
}