[C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘)

이 포스트에서는 O(N+M) 시간 문자열 탐색 알고리즘인 KMP 알고리즘에 대해 다루고 있습니다.

 

또한 KMP 알고리즘에 대해 설명하기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 16916번 : '부분 문자열' 문제의 풀이 코드와 해설을 다루고 있습니다. (문제의 난이도는 Solved.ac 기준 Gold III에 해당합니다.)

 

BOJ는 문제 자체가 특정 알고리즘을 구현하는 것을 목적으로 만들어진 것이 많기 때문에, 알고리즘에 대한 설명을 바로 예제를 풀면서 같이 정리하도록 하겠습니다.

 

 

16916번 : 부분 문자열

 

문자열 S와 검색할 부분 문자열 P가 순서대로 입력되었을 때, P가 S의 부분 문자열인지 검사하는 문제입니다.

문자열 S의 길이를 N, 부분 문자열 P의 길이를 M이라고 하였을 때 브루트포스 알고리즘으로 탐색할 경우 최악의 경우 O(NM)의 시간복잡도가 얻어지므로 100만 이하 길이의 문자열에 대해 적용하기는 적합하지 않습니다.

따라서 더 효율적인 O(N+M) 시간 알고리즘인 KMP 알고리즘을 구현해보도록 하겠습니다.

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
vector<int> Fail(string Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}
 
vector<int> KMP(string Str, string Pattern) {
    vector<int> Pi = Fail(Pattern), Pos;
    for(int i=0, j=0; i<Str.length(); i++) {
        while(j>0 && Str[i] != Pattern[j]) j = Pi[j-1];
        if(Str[i] == Pattern[j]) {
            if(j == Pattern.length()-1) {
                Pos.push_back(i-j);
                j = Pi[j];
            }
            else j++;
        }
    }
    return Pos;
}
 
int main() {
    string Str, Pattern;
    cin >> Str >> Pattern;
    vector<int> Pos = KMP(Str, Pattern);
    cout << !Pos.empty();
}
 

 

구현된 KMP 알고리즘의 형태는 위와 같습니다.

이 문제를 풀이하는데는 필요없지만, 최대한 일반화 되어있는 코드를 작성하고자, Pos 벡터에 검색을 통해 찾은 부분 문자열의 위치를 저장하여 반환하도록 하였습니다. (이후 벡터가 비어있는지만 확인해서 답을 출력하도록 하였음)

 

먼저 Fail 함수에서 Pattern[0] ~ Pattern[i]까지로 구성된 문자열에서 prefix = suffix인 가장 긴 문자열의 길이를 Pi 벡터에 저장하여 반환합니다.

이 과정에서의 탐색은 부분 문자열의 길이를 M이라고 할 때 O(M^2)으로 진행됩니다.

 

그 다음 KMP 함수에서는 위에서 구한 Pi 벡터를 활용하여, Str[i]와 Pattern[j]가 일치하지 않을 경우 다음 인덱스로 넘어가는 것(= 브루트포스 알고리즘)이 아니라, 최대 길이인 접두사 = 접미사인 위치로 skip하여 검사합니다. (이 과정을 통해 탐색 시간을 단축시키는 것)

만약 Str[i]와 Pattern[j]가 일치한다면 2가지 경우로 나뉘는데, j가 Pattern의 길이만큼 모두 탐색이 진행되었다면 Str 문자열이 Pattern의 문자열을 완전히 포함하고 있는 것이므로 해당 위치를 저장하든, 검색을 완료했다는 코드를 실행해주면 됩니다.

그 외의 경우에는 아직 부분 문자열의 중간까지 탐색한 것이므로 다음 자리도 일치하는지 확인해주면 됩니다.

 

 

 

코드를 제출해보면 위와 같이 정답 처리를 받을 수 있습니다.

iostream을 사용하지 않고 cstdio를 활용하거나, 아니면 속도를 빠르게 해주는 코드를 추가하면 40ms 정도에도 통과가 가능한 것으로 확인됩니다.

다음 포스트에서는 여기서 다룬 KMP 알고리즘을 베이스로 하여 다른 KMP 응용 문제들을 풀이해보도록 하겠습니다.