[백준/C++] 1786번 찾기 && kmp 알고리즘

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

1786번: 찾기

kmp 알고리즘에 관한 문제이다.

kmp 알고리즘이란, 문자열 패턴 매칭을 O(nm)이 아닌, O(n+m)에 해결할 수 있도록 해주는 문제이다.

이 알고리즘을 이해하기 위해서는, 접두사 접미사의 개념과 pi라고 칭한 이동경로 테이블을 왜 만드는지에 대한 이해가 필요하다.

이동경로 table은, 패턴의 부분 문자열(길이 1~원래 길이까지)마다 접두,접미사가 최대로 겹치는 길이를 저장해둔 table이다.

이것은 만약 패턴매칭을 하다가 중간에 매칭이 실패했을 경우, 현재까지 일치한 길이를 보고 얼마만큼 패턴을 이동시킬 것인지 결정하는 근거가 된다.

예를 들어 문장이 abcdabcdabee이고 패턴이 abcdabe라고 하자.

첫번째 a가 패턴의 첫 글자와 일치하므로 일단 검사를 시작할 것이다. b까지 일치하는 것도 확인할 수 있다. 그러다가 c까지 갔을 때, 패턴과 다름을 확인할 수 있다!

이때 패턴을 앞으로 이동시켜야 하는데, 이동거리 = 일치하는 패턴의 길이(6) - 패턴의 길이가 6일때 접두,접미사가 최대로 겹치는 길이(2) (abcdab가 일치하는데 이때 접두사(빨강)와 접미사(파랑)의 최대 겹치는 길이는 2이다.)

즉, 6 - 2 = 4 만큼 움직이면 된다.

쉽게 말해서 어느 한 부분이 다를 때, 그전까지 일치했던 부분에서의 꼬리와 머리가 가장 많이 일치하는 부분을 찾고, 패턴의 머리를 일치했던 부분의 꼬리로 움직여주면 된다

패턴의 머리를 인덱스 4의 위치로 움직여주고 다음 검사 시작하면 됨

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

string t,p;
vector<int> ans;
int pi[1000001];

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

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

    int j=0;
    // pi 배열은 접두사 접미사가 최대로 겹칠 때의
    for(int i = 1; i<p.size() ; i++){ // 접두사 접미사가 일치하는 최대 길이 구하기
        while(j > 0 && p[i] !=  p[j]) { // 다르면
            j = pi[j - 1]; // 일치할 때 까지 인덱스를 앞당김
        }
        if(p[i] == p[j])
            pi[i] = ++j; // 접두 접미사가 일치하는 최대 길이 저장
    }

    int m = p.size();
    j=0;
    for(int i = 0; i<t.size() ; i++){
        while(j > 0 && t[i] !=  p[j]) { // 다르면
            j = pi[j - 1];
        }
        if(t[i] == p[j]){
            if(j==m-1){ // 패턴 찾음
                ans.push_back(i-m+2); // 위치 저장
                j = pi[j];
            }else{
                j++;
            }
        }
    }

    cout << ans.size() << '\n';
    for(auto k : ans) cout << k << ' ';
    return 0;
}

---

kmp 알고리즘 참고 (정리가 정말 정말 잘 되어있다!)

https://chanhuiseok.github.io/posts/algo-14/#-2-2-kmp-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%88%9C%EC%84%9C

알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘