[C/C++] 백준 #1786 찾기(KMP)

이번 문제는 주어진 문자열에서 패턴 문자열을 모두 찾는 알고리즘을 작성하는 것입니다.

 

워드 프로세스 뿐 아니라, 이런 문제는 아주 다양한 곳에서 사용되고 있습니다.  서버에서도 기본적으로 문자열을 찾기 위해서 사용할 수 있는 것이라서, 해당 알고리즘을 알고 있으면 좋습니다.

 

전 이 물제를 풀기 위해서 KMP 알고리즘을 사용했습니다.  KMP 알고리즘이 구현하기 쉬워서 적용한 것은 아니고, 현재 사용할 수 있는 알고리즘 중에는 뛰어난 성능을 보여주는 알고리즘 중 하나이기 때문입니다.

 

KMP 알고리즘은 크게 두 부분으로 나누어집니다.  하나는 문자열 매칭에 실패했을 경우 건너띄는 pi 배열을 만드는 것이고, 다른 하나는 이 pi 배열을 이용해서 문자열에서 해당 패턴을 찾는 부분입니다.  pi 배열을 만드는 방법과 패턴 문자열을 찾는 알고리즘은 근본적으로 같습니다.  매칭 실패가 일어나면, 기존의 pi 배열을 이용해서 건너띄기를 하는 것이죠.

 

KMP 알고리즘을 이해하기 위해서는 접두사와 접미사의 개념을 알고 있어야 합니다.  예를 들어서 ababcab 란 문자열을 찾고자 합니다.  이 경우 글자수에 따라서 pi 배열을 구할 수 있습니다.  총 7글자이므로 8개의 배열을 만듭니다.  각각의 배열에는 숫자가 들어가게 되는데, 그 숫자의 의미는 다음과 같습니다.

 

인덱스	pstr[:i]	pi[]
0	''	0
1	'a'	0
2	'ab'	0
3	'aba'	1
4	'abab'	2
5	'ababc'	0
6	'ababca'	1
7	'ababcab'	2

사실 인덱스 0은 쓰이지 않기 때문에 굳이 안 만드셔도 됩니다.  전 글자수를 맞춘다는 의미로 인덱스 0을 넣었지만 사용하지는 않았습니다.

 

위와 같이 만들고서, 실제 사용하는 것은 두번째 글자부터입니다.  k개의 글자가 모두 맞고, k+1번째 글자가 틀렸다면, 우리는 빠르게 pi[]값을 이용해서 검사할 문자열을 옮깁니다.  예를 들어서 abababc 라는 문자열에서 검색하는 것이라면, 4개의 글자는 맞은 상태가 되고 5번째 글자는 c가 나와야하는데, a가 나왔습니다.  그러면 pi[4] 값을 이용해서 2로 옮깁니다.  그러면 패턴 문자열의 3번째 문자가 a이므로 넘어가게 되는 것이죠.  이렇게 하면 빠르게 틀린 글자를 처리할 수 있으므로, \(O(N+M)\) 정도의 알고리즘 효율을 얻을 수 있습니다.

 

KMP Algorithm

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//---------------------------------------------------------
//    baekjoon #1786
//        - by Aubrey Choi
//        - created at 2022-07-02
//---------------------------------------------------------
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> kmp(string tstr, string pstr)
{
    vector<int> r;
    int n = (int)tstr.size(), m = (int)pstr.size();
    int pi[m+1], j = 0;

    pi[1] = 0;
    for(int i = 1; i < m; i++)
    {
        while(j > 0 && pstr[j] != pstr[i]) j = pi[j];
        pi[i+1] = (pstr[j] == pstr[i])? ++j:0;
    }
    j = 0;
    for(int i = 0; i < n; i++)
    {
        while(j > 0 && pstr[j] != tstr[i]) j = pi[j];
        if(pstr[j] == tstr[i])
        {
            j++;
            if(j == m) r.push_back(i-m+1), j = pi[j];
        }
    }
    return r;
}

int main()
{
    string tstr, pstr;
    getline(cin, tstr);
    getline(cin, pstr);
    auto r = kmp(tstr, pstr);
    cout << r.size() << endl;
    for(auto t : r) cout << t+1 << " "; cout << endl;
}