KMP

문자열 매칭 알고리즘. O(N+M)

 

string parent, pattern;

KMP(parent,pattern) : pattern의 위치를 반환하는 함수

 

parent 문자열의 idx i, pattern 문자열의 idx j에 대해 i를 0부터 1씩 증가시키며 pattern을 찾는 상황에서 현재 i에서 pattern 찾는 것에 실패했을 때, i를 한 칸 옮기고 j를 fail[j]칸 옮기며 문자열을 찾는 알고리즘이다.

 

실패함수를 이용해서 푸는 문제가 많다.

 

실패함수를 만드는 로직과 kmp에서 pattern의 위치를 뽑는 로직이 같은 점을 눈여겨 보자.

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	for (int i = 1,j=0; 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 parentSize = parent.size();
	int patternSize = pattern.size();
	
	for (int i = 0,j=0; i < parentSize; i++) {
		while (j > 0 && parent[i] != pattern[j])
			j = table[j - 1];
		if (parent[i] == pattern[j]) {
			if (j == patternSize - 1) {
				printf("%d번째에서 찾음.\n", i - patternSize + 1);
				j = table[j];			
			}
			else ++j;
		}
	}
}

 

---

failure function = prefix function

 

문자열 s에 대해

pref[i] : i로끝나는 substr의 접두사=접미사 최대길이

string s,t;
vector<int> pref, ans;

int main() {
	FAST;
	getline(cin, s);
	getline(cin, t);

	pref.resize(t.size());
	for (int i = 1, j = 0; i < t.size(); i++) {
		while (j > 0 && t[i] != t[j]) j = pref[j - 1];
		if (t[i] == t[j]) pref[i] = ++j;
	}

	for (int i = 0, j = 0; i < s.size(); i++) {
		while (j > 0 && s[i] != t[j]) j = pref[j - 1];
		if (s[i] == t[j]) {
			if (j == t.size() - 1) {
				ans.push_back(i - t.size() + 1);
				j = pref[j];
			}
			else j++;
		}
	}

	cout << ans.size() << '\n';
	for (int i : ans) cout << i+1 << " ";
}