백준 1786 찾기

 

 

이 문제는 주어진 문자열과 T와 P가 주어질때 T에 P가 몇번 등장하는지 찾는 문제입니다.

 

문자열 최대길이가 100만이므로 단순히 찾는건 불가능이고 KMP 알고리즘을 이용하면 O(N) 만에 해결을 할 수 있습니다.  KMP 알고리즘은 종만북을 참고해서 공부했습니다. 처음에 이해가 조금 힘들었지만 테이블 그려보고 보다보면 이해가 되실겁니다!

 

P를 찾아야 하는 문자열이라고 하면 우리는 이 P에 대하여 pi 배열을 먼저 찾아주어야 합니다.(실패 함수라고 부르더라구요.) 

 

이떄 pi[i] 의 의미는 P의 부분 문자열 0~i의 접두사도 되고 접미사도 되는 최대 길이를 의미합니다. 우리는 이 배열을 이용해서 비교하지 않아도 되는 부분을 점프 할 수 있습니다.

 

pi 배열을 구하는 코드와 KMP를 구하는 코드의 함수는 거의 유사합니다. 다른점이 있다면 pi 배열을 구할때는 시작점을 1부터 시작하고 (첫문자끼리 비교하는건 포함하지 않기 때문입니다.) KMP를 구할때는 둘다 첫문자 부터 비교해야 하므로 시작점(begin이 0부터 시작입니다.)

 

matched 는 지금까지 일치한 문자의 개수를 의미하고

현재 begin+matched  == matched 의 문자가 일치한다면 matched를 증가시켜주며 진행해주면 되고 

KMP에서는 matched가 P와 같다면 begin을 답에 추가함으로써 부분문자열이 등장하는 시작위치를 찾을 수 있습니다.

Pi함수에서는  해당 위치에 pi배열에 matched 값을 넣어주면 됩니다. 

 

문자가 일치하지 않을경우 matched가 0이라면 begin을 다음칸으로 넘겨 주면 되고

matched가 0이 아니라면 matched - pi[begin+matched-1] 만큼 우리는 점프를 할 수 있으므로 (이전 위치에서는 부분 문자열이 만들어 질 수 없습니다.) 이값을 더해주면 됩니다. 이 점프한 위치는 답이 될 수 있는 begin의 위치이고 우리는 이 위치로부터 pi[begin+matched-1] 만큼이 이미 일치한다는 것을 알고 있으므로 matched에 이값을 넣어 줌으로써 이 비교 과정을 생략 할 수 있습니다.

 

자세한 설명은 다른 블로그 같은곳을 참고하시면 좋을 것 같습니다,,

 

다음은 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;



string N,M; //N이 바늘문자
vector<int> pi(1000000, 0);
vector<int> ans;

void getPi() { //Pi함수 전처리

    int begin = 1, matched = 0; //처음 자신과는 비교안함
    int n = N.size();

    while(begin + matched < n) {
        if(N[begin+matched] == N[matched]) {
            ++matched;
            pi[begin+matched-1] = matched;
        }
        else {

            if(matched == 0) begin++;
            else {
                begin += matched-pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
}

void kmp() {

    int begin = 0, matched = 0;
    int n = N.size();
    int m = M.size();

    while(begin <= m-n) {

        if(matched < n && M[begin+matched] == N[matched]) {
            matched++;
            if(matched == n) ans.push_back(begin); //begin을 시작으로 바늘문자열 존재
        }
        else {
            if(matched == 0) begin++;
            else {
                begin += matched-pi[matched-1];
                matched = pi[matched-1];
            }

        }
    }
}


int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    getline(cin, M);
    getline(cin, N);

    getPi();
    kmp();

    cout<<ans.size()<<'\n';
    for(auto it: ans) cout<<it+1<<' ';

    return 0;
}