백준[1786] 찾기

문제 설명

풀이

kmp알고리즘을 이용하여 풀 수 있다.

kmp를 학교 자료구조 시간에 배웠는데 실패 함수 부분이 이해가 안 되어 포기했는데 다시 천천히 생각하니 이해할 수 있었다.

실패함수

실패 함수도 kmp의 로직과 비슷하게 앞에서 비교한 것을 다시 비교하지 않고 재사용한다.

이해가 안된다면, abacabaac 이 예제로 실패 함수가 어떻게 돌아가는지 생각해보자.

코드

코드는 여기를 참고했다.

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

using namespace std;

vector<int> getPi(string p) {
    int m = p.size(), 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(), m = p.size(), 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 ans = kmp(s, p);
    printf("%lu\n", ans.size());
    for (auto i : ans) printf("%d ", i + 1);
}