KMP 알고리즘

Hyeon·2023년 8월 7일
KMP 알고리즘String Matching문자열 매칭
0

알고리즘

목록 보기
2/5

문자열 매칭

문자열이 주어졌을 때 특정한 패턴과 매칭되는 위치를 찾는 것을 말한다.

Brute Force 알고리즘

먼저 가장 단순한 방법을 떠올리자면, 모든 문자열의 위치에 대해 패턴을 하나하나 다 비교해보는 방법이다.

문자열의 길이를 N 패턴의 길이를 M 이라고 했을 때, 문자열의 각 위치에 대해 패턴을 모두 비교해야 하므로 O(NM)의 시간복잡도를 가진다.

KMP 알고리즘이란?

KMP 알고리즘이란 대표적인 문자열 매칭 알고리즘으로, 이전에 비교했던 정보를 이용하여 중복된 비교를 피해 시간복잡도를 줄인 알고리즘이다.

Failure Function

먼저, KMP 알고리즘의 핵심 배열인 Fialure Function 을 계산해놓은 배열을 준비해야 한다. Failure Function 이란 패턴의 prefix 와 suffix 가 일치하는 최대 길이를 의미한다.

j012345
P[j]abacab
F(j)001012

KMP

텍스트 abacaabaccabacab 와 패턴 abacab 를 매칭한다고 하자.

-012345678910111213141516
T-abacaabaccabacab
P-abacab

현재 4번째 텍스트인 a와 b가 다르다. 이때 다시 두번째 글자부터 패턴을 모두 매칭하는 것이 아니라, Failure Function 을 이용한다.

6번째 글자, 즉 index=5 에서 mismatch 가 발생했으므로 F(5-1) = 1 을 이용한다. 이 의미는 aba에서 proper prefix와 proper suffix 가 동일한 것은 "a" 이고 최대 길이가 1 임을 의미한다.

이 사실을 이용해서 우리는 아래와 같이 패턴의 인덱스를 F(5-1) = 1 로 점프해서 다시 패턴 매칭을 시도할 수 있다.

-012345678910111213141516
T-abacaabaccabacab
P-----abacab

이번엔 index = 1에서 mismatch 가 발생했다. 미리 구해놓은 Failure Function 에 의하면 F(1-0) = 0 이므로 패턴의 0번째 index 부터 다시 매칭을 시작한다. 이러한 방식으로 계속 패턴 매칭을 시도하면 아래와 같이 결과가 나온다.

-012345678910111213141516
T-abacaabaccabacab
P------abacab
P----------abacab
P-----------abacab

위와 같이 11번째 문자열에서 패턴과 일치함을 확인할 수 있다.

PseudoCode

Failure Function

FailureFunction(P)
    F[0] <- 0
    i <- 1
    j <- 0
    while i < m
        if P[i] = P[j]
            F[i] <- j + 1
            i <- i + 1
            j <- j + 1
        else if j > 0 then
            j <- F[j-1]
        else
            F[i] <- 0
            i <- i + 1

while 루프 안에서 2m 이상의 연산을 수행하지 않아, 시간복잡도는 O(m)이다.

KMP

KMP(T, P)
	F <- FailureFunction(P)
    i <- 0
    j <- 0
    while i < n
    	if T[i] = P[j]
        	if j = m - 1
            	return i - j
            else
            	i <- i + 1
                j <- j + 1
        else
        	if j > 0
            	j <- F[j-1]
            else
            	i <- i + 1
    return -1

Failure Function 연산은 O(m) 에 수행가능하고, while 루프 안에서 2n 이하의 연산을 수행한다. 따라서 시간복잡도는 O(n + m)이다.

예제

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

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define MX 1000000

// prefix, suffix 의 최대 길이
int lsp[MX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);

    int n = text.size();
    int m = pattern.size();

    // prefix suffix 배열 전처리
    int j = 0;
    for (int i = 1; i < m; i++)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = lsp[j - 1];
        }
        if (pattern[i] == pattern[j])
        {
            lsp[i] = ++j;
        }
    }

    // KMP 수행
    vector<int> pos;
    j = 0;
    for (int i = 0; i < n; i++)
    {
        while (j > 0 && text[i] != pattern[j])
        {
            j = lsp[j - 1];
        }
        if (text[i] == pattern[j])
        {
            if (j == m - 1) // 패턴이 모두 일치할 경우
            {
                pos.push_back(i - m + 2);
                j = lsp[j];
            }else{
                j++;
            }
        }
    }

    // 정답 출력
    cout << pos.size() << "\n";
    vector<int>::iterator it = pos.begin();
    for(; it != pos.end(); it++){
        cout << *it << " ";
    }cout << "\n";
}

출처

  • 교재 Computer Algorithms - Sara Baase, Allen Van Gelder
profile
Hyeon
컴공학부생입니다.
이전 포스트

0/1 Knapsack Problem

다음 포스트

Topologycal Sorting (위상 정렬)

0개의 댓글