[백준 1786번] 찾기 (C++ / KMP ** 어려웠음)

와 문제 엄청길다 ㅠㅠ 

KMP문제인데 이해하는데도 한참걸렸고, 사실 이해한건지 만건지 아직 잘 모르겠다.

KMP를 사용하지 않으면 O(n*m)의 시간복잡도를 가지지만, 패턴을 미리 만들어두면 거의 O(N)의 속도로 패턴 매칭을 찾을 수 있다.

간략하게 말하면 makeTable에서 접두사와 접미사에 대한 Table을 미리 만들어 두고, 이를 활용하여 kmp를 진행한다.

KMP에 대한 설명은 알고리즘 카테고리에서 다시한번 보도록 하자.

 

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

string n,m;
int result =0;
vector<int> result_vec;

vector<int> makeTable(string pattern){
    int patternSize = pattern.size();
    vector<int> table(patternSize,0);

    int j = 0 ; 
    for(int i = 1; i<patternSize; i++)
    {
        while(j >0 && pattern[i] != pattern[j]){
            j = table[j-1];
        }
        if(pattern[i] == pattern[j])
        {
            table[i] = ++j;
        }
    }
    return table;
}

void kmp(string parent, string pattern){
    vector<int> table = makeTable(pattern);
    int parentSize = parent.size();
    int patternSize = pattern.size();
    int j = 0;
    for(int i = 0 ; i< parentSize; i++)
    {
        while(j >0 && parent[i] != pattern[j])
        {
            //패턴이랑 parent랑 다를 동안에.
            //j 복귀 패턴.
            j=table[j-1];
        }
        //같을 때.
        if(parent[i] == pattern[j]){
            //온전하게 패턴 찾았을 때.
            if(j == patternSize -1){
                result_vec.push_back(i-patternSize+2); //어느위치에서 찾았는지 
                j = table[j]; // 패턴 째로 스킵.
                result ++; // 몇개 찾았는지.
            }else{
                //단순 매칭.
                j++; 
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    getline(cin,n);
    getline(cin,m);
    vector<int> table = makeTable(m);
    kmp(n,m);
    cout << result << endl;
    for(int i = 0 ; i< result_vec.size(); i++)
    {
        cout << result_vec[i] << " ";
    }
    
}