문자열 패턴 검색: 3 - KMP 알고리즘

설명

Knuth, Morris, Pertt이 만든 문자열 패턴 검색 알고리즘인 KMP 알고리즘은
O(n+m)에 문자열 패턴을 검색해낼 수 있다.

 

이 알고리즘의 핵심은 lps 배열이다.

lps = Longest Prefix Suffix.

각 위치까지의 부분 문자열에서 자기 자신의 접두사이면서 접미사인 가장 긴 길이를 저장한 배열이다.

패턴 내에서 일치하지 않는 문자가 발견되면, 이전에 계산한 lps를 이용하여 패턴을 적절히 이동한다.

lps[i]는 0부터 i-1까지는 

 

 

LPS 배열의 생성방법은 다음과 같다:

lps[0]와 len을 0으로 초기화한다. len은 가장 긴 접두사와 접미사 값의 길이이다.

pat[len]과 pat[i]가 일치하면, len을 1 증가하고, 증가된 값을 lps[i]에 할당한다.

일치하지 않고 len이 0이 아니면, len을 lps[len-1]로 업데이트한다.

일치하지 않고 len이 0이면, lps[i]를 0으로 초기화한다.

 

문자열 "ABABAC"를 예로 들어보자.

lps[0] = 0, len = 0, i = 0으로 시작,

i = 1로 이동.

 

pat[0] != pat[1]이고, len = 0이므로, lps[1] = 0이다.

i = 2로 이동.

 

pat[0] == pat[2]이므로, len++, lps[2] = len이다.

len은 1이 되고, lps[2] = 1, i = 3으로 이동.

 

pat[1] == pat[3]이므로, len++, lps[3] = len이다.

len은 2가 되고, lps[3] = 2, i = 4로 이동.

 

pat[2] == pat[4]이므로, len++, lps[4] = len이다.

len은 3이 되고, lps[4] = 3, i = 5로 이동.

 

pat[3] != pat[5]이고, len > 0이므로, len = lps[len-1], lps[5] = 0/

len은 lps[2] = 1이 되고, lps[5] = 0.

 

 

KMP 알고리즘의 동작은 다음과 같다:

Naive 알고리즘과는 달리, lps[]의 값을 이용하여 다음에 매치할 문자를 결정할 수 있다.

핵심은 "어차피 매치되는 게 확실한 부분은 매치하지 않는다"이다.

 

어떻게 lps[]로 다음 위치를 결정하고, 건너뛸 문자 수를 알아내냐면..

1. j = 0인 pat[j]와 현재 텍스트 창의 문자와 비교를 시작한다.
2. txt[i]와 pat[j] 문자를 계속 일치시키고, 계속 그런 동안 계속 증가시킨다.
3. 만약 일치하지 않는다면..
   
   • pat[0...j-1]과 txt[ij...i-1]은 일치한다는 것을 이미 알고 있다.
   • 또한, lps[j-1]이 pat[0...j-1]의 접두사와 접미사 모두에 해당하는 문자의 개수라는 것을 알고 있다.
   • 결론적으로, lps[j-1]문자를 txt[ij...i-1]과 매치할 필요가 없음을 알 수 있다.

 

코드(C++)

#include <iostream>
#include <vector>
using namespace std;

void computeLPSArray(string &pat, int M, vector<int> &lps)
{
    int len = 0;

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

vector<int> KMPSearch(string &pat, string &txt)
{
    int M = pat.length();
    int N = txt.length();

    vector<int> lps(M);

    vector<int> result;

    computeLPSArray(pat, M, lps);

    int i = 0;
    int j = 0;
    while ((N - i) >= (M - j))
    {
        if (pat[j] == txt[i])
        {
            j++;
            i++;
        }

        if (j == M)
        {
            result.push_back(i - j + 1);
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i])
        {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return result;
}

int main()
{
    string txt = "hello from the other side hell yeah hello";
    string pat = "hell";
    vector<int> result = KMPSearch(pat, txt);

    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    return 0;
}

 

복잡도 분석

O(n+m)의 시간복잡도를 갖는다. m은 패턴의 길이, n은 전체 텍스트의 길이이다.

사실상 O(n)이라고 봐도 된다. n > m이기 때문에, O(1.99999.. * n) -> O(n)

공간 복잡도는 O(m) lps배열은 패턴의 길이에 의존한다.

 

참조

https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/