KMP 알고리즘

반응형

 

<KMP 알고리즘>

 

주로 문자열 관련 패턴을 찾는 알고리즘으로 대표적인 2가지가 있다.

바로 Hashing에 기반한 Rabin-Karp 알고리즘과 KMP알고리즘이다.

Rabin-Karp알고리즘은 해시를 사용해 두 문자열의 해시 값을 구해 이둘을 비교하는 방식으로 오차를 감안하고 찾는다.

해시 값이 다르면 두 문자열은 100% 다르다는 것이지만, 해시값이 같다면 두 문자열은 같을 수 도 있다는 점에서 정확도가 100%가 아니다.

대신, 이전 계산한 부분 문자열의 해시값을 이용해 현재 해시값을 빠르게 구할 수 있기 때문에 탐색 속도가 빠르다.

대표적인 공식은 다음과 같다.

길이가 M인 패턴 P=p1*p2*p3*....pm에 대해

f(p1)=p(m)+p(m-1)*a+p(m-2)*a^2+....p(1)*a^m-1

f(p2)=p(m+1)+p(m)*a+p(m-1)*a^2+....p(2)*a^m-1

 

따라서, 두 공식에 a를 곱하면 F(p(2))=a*F(p(1)) + p(m+1) - p(1)*a^m 으로 정리할 수 있다.

여기서, T의 각 위치에서 해시값을 구하는 시간복잡도가 O(1)이고, P의 해시값을 찾을때 O(M)만에 구할 수 있으므로, 총 시간복잡도는 O(N+M)이다. 

 

반면, KMP 알고리즘은 패턴 P를 최대 얼마나 이동시킬 수 있을 지를 결정하는 KMP실패함수를 통해 매칭에 실패했을 때, 이전에 성공한 부분을 다시 이용한다.

그래서 해시를 사용하여 부분 문자열을 탐색하는 라빈카프 알고리즘에 비해서 정확도가 높다!!

또, Naive한 알고리즘에서 이미 비교한 패턴을 건너 뛰며 탐색하기 때문에 속도도 빠르다. 하지만, 라빈카프 알고리즘 보단 빠르진 않다.

 

속도비교 : 기본비교하며탐색(Naive한 알고리즘) < KMP알고리즘 < Rabin-Karp 알고리즘

 

다음은 전형적인 KMP알고리즘을 사용해 문자열에서 패턴이 몇번 나왔는지, 해당 패턴들에 대한 첫 인덱스들을 출력하는 문제이다.

 

# BOJ 1786번:찾기

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
 
const int MAXLEN = 1000000 + 1;
string T;
string P;
int n, m;
int pi[MAXLEN];
vector<int> v;
 
void getpi() {
    memset(pi,0,sizeof(pi));
    int j = 0;
    pi[0] = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && P[i] != P[j]) {
            j = pi[j - 1];
        }
        if (P[i] == P[j]) {
            //j++;    //앞에 몇 글자 맞았는지 판단하는 인덱스
            pi[i] = ++j;
        }
        //pi[i] = j;
    }
}
int main() {
    int i, j;
 
    cin.clear();
    getline(cin, T);
    getline(cin, P);
    n = T.length();
    m = P.length();
 
    getpi();    // KMP실패함수 구하기
 
    //i : 전체 문자열과 비교할 인덱스
    //j : 찾을 문자열의 비교 인덱스
    j = 0;
    for (i = 0; i < n; i++) {
        while (j > 0 && T[i] != P[j]) {
            j = pi[j - 1];    //KMP실패함수를 통해 패턴이 같지 않다면 j를 앞으로 이동시킴
        }
        if (T[i] == P[j]) {
            if (j == m - 1) {    //패턴의 끝에 도달 했을 경우
                v.push_back(i - j +1);    //찾은 패턴 한개의 시작 인덱스를 푸쉬
                j = pi[j];    //여러개 문자열을 찾을 수 있기 때문
            }
            else {
                j++;
            }
        }
    }
    printf("%d\n", v.size());
    for (i = 0; i < v.size(); i++) {
        printf("%d\n", v[i]);
    }
    return 0;
}