[백준 1786] 찾기

 

 

 문자열 매칭 문제. 문제에서 설명하고 있는 건 KMP 알고리즘인데, 문득 보이어-무어 알고리즘이 떠올라서 그걸 먼저 시도했다. Bad Character 방법만 이용해서 구현했는데, 모든 테스트 케이스나 반례를 다 통과함에도 이상하게 제출만 하면 자꾸 바로 틀렸습니다가 나와서 원인을 결국 못 찾았다. 나중에 여유가 생겼을 때 다시 확인해봐야 할 것 같다.

 그래서 그냥 문제에 있는 KMP 알고리즘을 그대로 구현했더니, 바로 통과할 수 있었다. 탐색을 생략할 수 있는 길이를 알아낼 수 있도록 미리 전처리해서 pi 배열을 만들었고, 탐색할 때도 이를 활용해 적절하게 불필요한 탐색 구간을 뛰어넘도록 했다. 문제에서 설명하는 대로 패턴 문자열의 중복되는 부분을 이용하여 매칭 실패가 발생했을 때, 앞에서 일치했던 부분의 중복된 부분을 당겨와 매칭을 이어나가는 식으로 구현하면 된다. 사실 글로 이해하기는 난해한 부분이 있고 직접 구현해서, 매칭 과정을 들여다보는 것이 더 이해하기 쉬울 것이다.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string n = "", m = "";
    getline(cin, n);
    getline(cin, m);

    //pre-processing
    vector<int> pi(m.size(), 0);
    int piInd = 0;
    for(int i=1; i<m.size(); i++) {
        while(piInd>0 && m[i]!=m[piInd]) {
            piInd = pi[piInd-1];
        }
        if(m[i]==m[piInd]) {
            pi[i] = ++piInd;
        }
    }

    //search
    vector<int> matchedInd;

    piInd = 0;
    for(int i=0; i<n.size(); i++) {
        while(piInd>0 && n[i]!=m[piInd]) {
            piInd = pi[piInd-1];
        }
        if(n[i]==m[piInd]) {
            if(piInd == m.size()-1) {
                matchedInd.push_back(i-piInd+1);
                piInd = pi[piInd];
            } else {
                piInd++;
            }
        }
    }

    cout << matchedInd.size() << "\n";
    for(int& ind: matchedInd) {
        cout << ind << " ";
    }
}