백준 1786번 찾기

KMP 알고리즘을 이용해서 풀 수 있는 문제다.

 

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

1786번: 찾기

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

using namespace std;

string s, t;
int cnt;
vector<int> position, pi;

void getPi();
void KMP();

int main(void) {

	char c;
	while ((c = getchar()) != '\n') {
		s += c;
	}
	
	while ((c = getchar()) != '\n') {
		t += c;
	}

	getPi();
	KMP();

	cout << position.size() << '\n';
	for (auto i : position) {
		cout << i << '\n';
	}
	return 0;
}

void getPi() {
	pi.resize(t.size(), 0);

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

		if (t[i] == t[j]) {
			pi[i] = ++j;
		}
	}
}

void KMP() {
	int j = 0;
	for (int i = 0; i < s.size(); i++) {
		while (j > 0 && s[i] != t[j]) {
			j = pi[j - 1];
		}

		if (s[i] == t[j]) {
			if (j == t.size() -1) {
				j = pi[j];
				position.push_back(i - t.size() + 2);
			}
			else {
				j++;
			}
		}
	}
}