KMP 문자열 탐색 알고리즘

KMP 문자열 탐색 알고리즘

글 안에서 단어를 빠르게 찾거나, 문자열을 전처리하여 우리가 원하는 정보를 추출하는 알고리즘은 여러 분야에서 활용이 가능하다.

 

대표적인 문자열 안에서 단어를 찾는 문자열 탐색 알고리즘으로는

• 라빈-카프
• 보이어-무어
• KMP 알고리즘

등이 있으며, 문자열 안에서 여러 개의 단어를 동시에 찾는 방법으로 아호-코라식 알고리즘이 있다.

 

가장 간단한 문자열 탐색

문자열 안에서 특정 단어를 검색하는 가장 간단한 방법은 전부 하나하나 비교하는 것이다.

 

 

위처럼 원본 문자열의 맨 앞 문자부터 탐색을 시작하여, 탐색 문자열과 다른 문자가 발견되다면 두 번째 문자부터 다시 비교하는 과정을 계속 반복하는 아주 간단한 방법이다.

 

 

위처럼 탐색 문자열을 원본 문자열의 모든 부분에 대해서 비교하는 방식은 매우 간단하지만 그만큼 매우 느리다.

 

 

KMP 알고리즘의 기본 아이디어는 여기에서 시작된다. 계속 반복되는 부분을 건너 뛸 순 없을까?

 

KMP 알고리즘의 아이디어

 

KMP 알고리즘에서 정의하는 접두사와 접미사란, 문자열에서 맨 앞과 맨 뒤에 같은 문자열이 나오는 경우를 말한다.

 

접두사와 접미사가 같으면 그만큼 건너뛰는게 가능해진다!

 

여기서 얻을 수 있는 결론은 탐색 문자열의 앞부분과 원본 문자열의 뒷부분이 동일한 부분까지는 문자열 탐색을 건너뛸 수 있다는 사실이다.

 

이를 위해서 KMP 알고리즘은 탐색 문자열의 접두사와 접미사를 계산해야 할 필요가 있습니다.

 

접두사 접미사를 계산하는 GetPi 함수

static List<int> GetPi(string s)
{
    List<int> list = new List<int>();

    for (int i = 1; i <= s.Length; i++)
    {
        var slice = s.Substring(0, i);

        var matchingLength = 0;
        var startIndex = 0;

        while (startIndex <= slice.Length / 2)
        {
            var t1 = slice.Substring(0, startIndex + 1);
            var t2 = slice.Substring(slice.Length - t1.Length, t1.Length);

            if (t1 == t2)
            {
                matchingLength = t1.Length;
            }

            startIndex++;
        }

        list.Add(matchingLength);
    }

    return list;
}

 

begin 에다가 match를 더해준 뒤, pi[match - 1]를 빼주면 KMP 알고리즘의 아이디어대로 접두사, 접미사가 일치하는 다음 탐색 위치로 이동이 가능하다.

 

• begin을 match - pi[match - 1]만큼 더해서 이동
• match를 pi[match - 1]의 값으로 대입

 

예제 코드

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var list = KMP("abababab", "abab");

        Console.WriteLine(string.Join(",", list));
    }

    static List<int> KMP(string s, string pattern)
    {
        var piList = GetPi(s);
        var list = new List<int>();

        int begin = 0;
        int match = 0;

        while(begin + match < s.Length)
        {
            if (match < pattern.Length && s[begin + match] == pattern[match])
            {
                match++;

                if (pattern.Length == match)
                {
                    list.Add(begin);
                }
            }
            else
            {
                if (match == 0)
                {
                    begin++;
                }
                else
                {
                    // 가장 중요한 부분!
                    begin += match - piList[match - 1];
                    match = piList[match - 1];
                }
            }
        }

        return list;
    }

    static List<int> GetPi(string s)
    {
        List<int> list = new List<int>();

        for (int i = 1; i <= s.Length; i++)
        {
            var slice = s.Substring(0, i);

            var matchingLength = 0;
            var startIndex = 0;

            while (startIndex <= slice.Length / 2)
            {
                var t1 = slice.Substring(0, startIndex + 1);
                var t2 = slice.Substring(slice.Length - t1.Length, t1.Length);

                if (t1 == t2)
                {
                    matchingLength = t1.Length;
                }

                startIndex++;
            }

            list.Add(matchingLength);
        }

        return list;
    }
}

 

참조 사이트

Injae's devlog