KMP 알고리즘

[devLupin]

• 어떠한 텍스트 t와 패턴 p가 주어졌을 때
• t 안에 p 패턴이 있는지 확인하는 방법
• 패턴 문자열 p의 접두사와 접미사의 일치 부분을 계산하는 failure 함수 이용
• 시간복잡도
  • 단순 탐색 : $O(T*P)$
  • KMP : $O(T+P)$

[devLupin]

• 단순히 있는지 없는지 판단할 때

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

string t, p;
vector<int> f, ans;

void failure(string &s) {
	f.assign(s.size(), 0);
	int j = 0;
	for(int i = 1; i < s.size(); i++) {
		while(j > 0 && s[i] != s[j]) j = f[j-1];
		if(s[i] == s[j]) f[i] = ++j;
	}
}

bool solve() {
	int j = 0;
	for(int i = 0; i < t.size(); i++) {
		while(j > 0 && t[i] != p[j]) j = f[j-1];
		if(t[i] == p[j]) j++;
		if(j == p.size()) return 1;
	}
        return 0;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	getline(cin, t);
	getline(cin, p);

	failure(p);
	cout << solve() // 1이면 패턴이 존재하는 것.

	return 0;
}

[devLupin]

• 패턴의 개수 및 시작 위치를 찾고 싶을 때

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

string t, p;
vector<int> f, ans;

void failure(string &s) {
	f.assign(s.size(), 0);
	int j = 0;
	for(int i = 1; i < s.size(); i++) {
		while(j > 0 && s[i] != s[j]) j = f[j-1];
		if(s[i] == s[j]) f[i] = ++j;
	}
}

void solve() {
	int j = 0;
	for(int i = 0; i < t.size(); i++) {
		while(j > 0 && t[i] != p[j]) j = f[j-1];
		if(t[i] == p[j]) j++;
		if(j == p.size()) {
			ans.push_back(i-j+1);
			j = f[j-1];  // 이후 다시 탐색해야 하므로, j-1로
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	getline(cin, t);
	getline(cin, p);

	failure(p);
	solve();

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

	return 0;
}