[알고리즘 - 문자열 처리] KMP

KMP 알고리즘은 한 문자열(s)에 다른 문자열(p)이 몇번 나타나는지를 확인 할 수 있는 알고리즘이다. 문자열 p 의 앞과 뒤가 얼마나 같은지 미리 확인한 다음 두 문자열 s 와 p를 확인하다가 맞지 않는 부분이 나오면 한칸 옮기는 것이 아니라 겹치는 부분을 제외하고 넘어 갈 수 있다. 

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

vector<int> getPi(string p) {
	int m = p.size();
	int j = 0;
	vector<int> pi(m, 0);
	for (int i = 1; i < m; i++) {
		while (j > 0 && p[i] != p[j])
			j = pi[j - 1];
		if (p[i] == p[j])
			pi[i] = ++j;
	}
	return pi;
}

vector<int> kmp(string s, string p) {
	vector<int> ans;
	auto pi = getPi(p);
	int n = s.size();
	int m = p.size();
	int j = 0;
	for (int i = 0; i < n; i++) {
		while (j > 0 && s[i] != p[j]) {
			j = pi[j - 1];
		}
		if (s[i] == p[j]) {
			if (j == m - 1) {
				ans.push_back(i - m + 1);
				j = pi[j];
			}
			else {
				j++;
			}
		}
	}
	return ans;
}


int main() {
	string s, p;
	getline(cin, s);
	getline(cin, p);
	auto matched = kmp(s, p);
	cout << matched.size() << "\n";
	for (auto i : matched) {
		cout << i+1 << "\n";
	}
	return 0;
}

 

 

참조 : https://bowbowbow.tistory.com/6