백준: Class 6 - 1786(KMP 알고리즘)

</br> KMP 알고리즘을 정리해 보자
1786번 문제 내용 자체도 kmp 알고리즘을 설명하고 있다
</br>

찾는 문자열 내 반복 찾기

    int psz = p.size();
    vector<int> pi(psz, 0);
    int start = 1, matched = 0;
    while( start + matched < psz ){
        if( p[start + matched] == p[matched] ){
            matched++;
            pi[start + matched - 1] = matched;
        }
        else{
            if( matched == 0 ) start++;
            else{
                start += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }

일단 가장 처음이 반복될 수는 없으니 인덱스는 1부터 시작한다.
만약 p[start + matched] == p[matched]라면, 현재 일치한다는 뜻이므로 matched를 ++하고, pi[start + matched - 1]]에 matched를 기록한다.
만약 다를 경우, matched가 0이면 시작 부분을 뒤로 한 칸 민다.
matched가 있는 경우, 시작 부분은 그 만큼 넘어간다.

        0123456
ex) p = ABCDABD
s m
2 0
3 0
4 0
4 1   < p[0] = A와 매치
4 2   < p[1] = B와 매치
6 0   < matched가 있었으므로 시작 부분을 그 뒤로 민다
7 0
pi: 0 0 0 0 1 2 0

</br>

문자열 찾기

    matched = 0;
    for(int i = 0; i < t.size(); i++){
        while( matched > 0 && t[i] != p[matched] ){
            matched = pi[matched - 1];
        }
        if( t[i] == p[matched] ){
            matched++;
            if( matched == psz ){
                ans.push_back(i - psz + 2);
                matched = pi[matched - 1];
            }
        }
    }

matched = pi[matched - 1];로 탐색할 인덱스를 정한다.
만약 현재 t[i]가 p[matched]와 같은 경우, matched++한다. 만약 이 맞은 개수가 p의 크기와 같다면 찾은 것이므로 답에 추가한다.

</br>

1786: 찾기

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

#include <bits/stdc++.h>
#define P pair<int, int>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string t, p;
    getline(cin, t);
    getline(cin, p);

    int psz = p.size();
    vector<int> pi(psz, 0);
    int start = 1, matched = 0;
    while( start + matched < psz ){
        if( p[start + matched] == p[matched] ){
            matched++;
            pi[start + matched - 1] = matched;
        }
        else{
            if( matched == 0 ) start++;
            else{
                start += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }

    vector<int> ans;
    matched = 0;
    for(int i = 0; i < t.size(); i++){
        while( matched > 0 && t[i] != p[matched] ){
            matched = pi[matched - 1];
        }
        if( t[i] == p[matched] ){
            matched++;
            if( matched == psz ){
                ans.push_back(i - psz + 2);
                matched = pi[matched - 1];
            }
        }
    }

    cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << '\n';
    }

}

전체 코드는 위와 같다.
</br>

---

새로운 게 많다
</br>