백준 16916번: 부분 문자열 (C++)

https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

---

Solved By: KMP

 

첫 KMP 문제였습니다. 설명으로 적어내긴 어렵고, 아직 확실히 정복하지는 못 한 거 같습니다. 그래도 이해한 대로 주석을 달아두었습니다.

 

#include <iostream>
#include <vector>
using namespace std;

// '문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용
// 주어진 패턴(문자열)의 0 ~ i 부분 문자열까지
// 접두사와 접미사의 최대 일치 길이를 담은 배열
vector<int> getPi(string s){
    int patternSize = s.size();
    vector<int> pi(patternSize, 0);
    
    for(int i = 1, j = 0; i < patternSize; i++){
        // 일치하지 않으면 직전 상황의 문자를 참고하여
        // 같은지의 여부를 따짐
        while(j > 0 && s[i] != s[j]) j = pi[j - 1];
        // 같은 경우 i, j 둘 다 늘어나게 된다.
        // j가 접두사와 접미사의 일치 길이를 나타내므로
        // pi[i]에 ++j를 할당한다.
        if(s[i] == s[j]) pi[i] = ++j;
    }
    
    return pi;
}

bool kmp(string s, string p){
    vector<int> pi = getPi(p);
    vector<int> ans;
    int n = s.size(), m = p.size();
    for(int i = 0, j = 0; i < n; i++){
        while(j > 0 && s[i] != p[j]) j = pi[j - 1];
        if(s[i] == p[j]){
            // pattern을 찾은 경우
            if(j == m - 1){
                return 1;
                ans.push_back(i - m + 1);
                j = pi[j];
            }
            else j++;
        }
    }
    return 0;
}

int main(){
    string s; cin >> s;
    string p; cin >> p;
    
    cout << kmp(s, p);
    
    return 0;
}