[BOJ 백준] 1786번 찾기

문제

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

1786번: 찾기

접근

정석으로 KMP 알고리즘을 사용하여 풀이를 요구하는 문제이다.

KMP알고리즘에 관한 건 이전에 풀었던 문제인 [BOJ 백준] 1305번 광고 포스팅을 참고하시길 바란다.

코드

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

using namespace std;

int main() {
    string t, p;
    getline(cin, t);
    getline(cin, p);
    vector<int> fail(p.size(), 0), answer;
    for (int i = 1, j = 0; i < p.size(); i++) {
        while(j > 0 && p[i] != p[j])
            j = fail[j - 1];
        if (p[i] == p[j])
            fail[i] = ++j;
    }

    for (int i = 0, j = 0; i < t.size(); i++) {
        while(j > 0 && t[i] != p[j])
            j = fail[j - 1];
        if (t[i] == p[j]) {
            if (j == p.size() - 1) {
                answer.push_back(i + 1 - j);
                j = fail[j];
            }
            else j++;
        }
    }
    cout<<answer.size()<<"\n";
    for (int i = 0; i < answer.size(); i++) {
        cout<<answer[i]<<" ";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study