[BOJ 1786] 찾기

https://www.acmicpc.net/problem/1786

1786번: 찾기

입력

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.

출력

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.

---

접근법

https://parvegoongame.tistory.com/70

[문자열 매칭 알고리즘 #1] KMP 알고리즘

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	int j = 0;
	for (int i = 1; i < patternSize; i++) {
		// 서로 다르면, 중복되는 부분 띄어넘기
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
			
		}
		// 같으면 + 1
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

vector<int> kmp(string parent, string pattern) {
	vector<int> ans;

	auto table = makeTable(pattern);
	int parentSize = parent.size();
	int patternSize = pattern.size();
	int j = 0;

	for (int i = 0; i < parentSize; i++) {
		// 서로 다르면, 중복을 제외한 부분 건너띄기
		while (j > 0 && parent[i] != pattern[j])
			j = table[j - 1];
		
        // 같을때 +1, 만약 패턴을 찾으면 찾은 위치 기억
		if (parent[i] == pattern[j]) {
			if (j == patternSize - 1) {
				ans.push_back( i - patternSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string parent, pattern;
	getline(cin, parent);
	getline(cin, pattern);

	auto res = kmp(parent, pattern);

	cout << res.size()<<"\n";
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << "\n";
	}
}