KMP

대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다.

 

가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에 대해 알아봅시다.

 

문자열을 검색하는 가장 단순한 방법은, 이중 포문을 돌려 \(O(|S||T|)\)의 시간복잡도로 검색하는 것입니다.

 

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

1786번: 찾기

 

하지만 \(S\)와 \(T\)의 길이가 각각 최대 100만이라면 어떨까요?

 

더 빠른 검색을 위해, \(O(|S|+|T|)\)의 속도로 문자열을 검색할 수 있는 KMP알고리즘에 대해 알아봅시다.

 

 

\(S\) = "ABCABCABDEAB"

\(T\) = "ABCABDE"

라고 하고, \(S\)에서 \(T\)를 찾으려고 합니다.

 

6번째 인덱스에서 서로 다른 문자가 있기 때문에, 1번 인덱스부터 시작하는 \(S\)의 부분 문자열은 \(T\)가 아닙니다.

 

나이브하게 진행한다면 2번 인덱스부터 시작해서 다시 \(T\)를 검색했겠지만, KMP는 그렇지 않습니다.

 

지금까지 검색한 문자열 "ABCAB"에 대해 \(T\)가 또 등장할 가능성이 있는 시작 인덱스를 찾아 거기서부터 다시 검색을 시작합니다.

 

위의 예시 같은 경우는 "ABCAB"까지는 맞는 문자열이었으니, 뒤의 "AB"부터 시작하면 맞는 문자열을 찾을 가능성이 생기게 됩니다.

 

따라서 \(S\)의 4번째 인덱스부터 시작해 검색하고, \(T\)의 2글자까지는 매칭이 완료되었다고 생각할 수 있습니다.

그리고 그 다음인 \(S\)의 6번째 인덱스와 \(T\)의 3번째 인덱스가 맞는지 매칭을 계속하게 됩니다.

 

이와 같이 우리가 찾으려는 문자열에 대해, 각 인덱스에서 검색을 실패했을 때 다음으로 검색하면 되는 인덱스를 저장해 두면

\(O(|S|+|T|)\)의 시간복잡도로 검색을 할 수 있음을 알 수 있습니다.

 

이를 KMP의 실패 함수(failure function)이라고 합니다.

그리고 위의 예시에서 눈치채신 분들도 계시겠지만, 실패 함수는 \(T\)의 부분 문자열 \(T[1...i]\)에서 접두사와 접미사가 같은 최대길이를 저장하고 있습니다.

 

그러면 이 실패 함수는 어떻게 만들 수 있을까요?

 

사실 실패 함수조차도 이 아이디어를 사용해 만들 수 있습니다.

\(T\)에서 \(T\)를 찾으면 됩니다.

 

당연히 맨 앞인 1번 인덱스부터 \(T\)를 찾으면 자기 자신을 찾을 테니, 2번 인덱스부터 시작합시다.

 

첫 글자부터 다르다면 겹치는게 없으니 0이고, 그렇지 않다면 현재까지 일치한 문자 개수가 자기자신의 접두사와 접미사가 같은 최대 길이입니다.

 

그렇게 5번 인덱스까지 실패함수를 만들었는데, 6번 인덱스에서 문자가 일치하지 않습니다. 이 다음은 어떻게 해야 할까요?

현재 문자 2개까지 매칭에 성공했으니, 2번 인덱스의 실패 함수에 따라 행동하면 됩니다.

2번 인덱스의 실패함수는 이전에 계산해 뒀기 때문에 (0), 아무 문제없이 검색을 진행할 수 있습니다.

 

이렇게 \(T\)에서 \(T\)를 검색하며 실패 함수를 만든 다음, 실패 함수를 이용해 다시 \(S\)에서 \(T\)를 검색하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
string S, T;
int back[1000001]; // 실패 함수
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    getline(cin, S);
    getline(cin, T);
 
    back[0] = -1;
    int ptr = -1; // 현재 검색하고 있는 T의 인덱스
 
    for (int i = 0; i < T.size();) // T에서 T를 찾는다.
    {
        while (ptr != -1 && T[i] != T[ptr]) ptr = back[ptr];
        back[++i] = ++ptr;
    }
 
    vector <int> ans;
 
    ptr = 0;
    for (int i = 0; i < S.size();)
    {
        while (ptr != -1 && S[i] != T[ptr]) ptr = back[ptr];
        ++i, ++ptr;
 
        if (ptr == T.size()) ans.push_back(i - T.size() + 1);
        // T를 찾았다.
    }
 
    cout << ans.size() << '\n';
    for (int it : ans) cout << it << '\n';
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217