문제 출처

1. 문제설명

  • 문제가 매우 길지만, 결국 KMP를 구현하는 문제
  • 어떤 문자열 패턴 T가 주어질 때 패턴 P가 있는지?
    • 있다면 몇 번 등장하고 처음 시작위치는 어디인지 출력
  • 문제 분류
    • Graph, KMP


2. 알고리즘 설계

  • KMP 기본 문제이다.
  • 접두사 접미사를 이용한 실패함수 구현이 핵심이다.
  • KMP를 반드시 써야하는 상황이 있는데, 그게 바로 접두사, 접미사를 이용한 뭔가를 할 때이다.
  • 만약 단순히 패턴을 찾는다면, 아래 if문에서 바로 리턴시키면 되고,

  • 패턴 여러개를 찾는다면, j = f[j-1];와 같이 위치를 다시 갱신시켜야 한다.

    if(j == p.size()) {
	ans.push_back(i-j+1);
	j = f[j-1];
}


3. 전체 코드

#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];
		}
	}
}

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;
}