[C++] KMP 알고리즘 구현

#include <iostream>
#include <string>
#include <string_view>
#include <vector>

using namespace std;

// Knuth-Morris-Pratt Algorithm
// bush의 앞에서부터 needle의 최초 위치를 찾아 반환합니다.
size_t kmp(string_view bush, string_view needle)
{
    const size_t needleLen = needle.length();
    const size_t bushLen = bush.length();
    
    // string::find는 패턴 문자열이 비어있을 경우 0을 반환함.
    if (needleLen == 0)
    {
        return 0;
    }


    // pi[match] == needle[:match+1]의 최대 동일 접두접미사 길이
    vector pi(needleLen, 0ul);

    for (size_t i = 1, match = 0; i < needleLen; ++i)
    {
        while (match > 0 && needle[i] != needle[match])
            match = pi[match - 1];
        if (needle[i] == needle[match])
            pi[i] = ++match;
    }
    
    
    for (size_t i = 0, match = 0; i < bushLen; ++i)
    {
        // 매치 실패시
        // 성공할 때까지 혹은 더 이상 할 수 없을 때까지 건너뛰기 시도.
        while (match > 0 && bush[i] != needle[match])
        {
            match = pi[match - 1];
        }
        
        // 매치 성공시
        // 다음 문자 검색 준비.
        // 다음 문자가 없다면 검색이 완료된 것이므로 위치 계산 후 반환.
        if (bush[i] == needle[match])
        {
            ++match;
            if (match >= needleLen)
            {
                // i를 반환하지 않고 이러는 이유는
                // 현재 i가 검색된 문자열의 뒤를 가리키고 있기 때문임.
                return i - (match - 1);
            }
        }
    }
    
    
    // 찾을 수 없음.
    return string::npos;
}

int main()
{
    string bush;
    string needle;
    
    getline(cin, bush);
    getline(cin, needle);
    
    size_t index = kmp(bush, needle);
    size_t answer = bush.find(needle);
    
    // 구현 검증
    if (answer != index)
    {
        cout << "FAIL! Answer : " << answer << ", Me : " << index << endl;
        return -1;
    }
    
    if (index == string::npos)
    {
        cout << "Couldn't find!" << endl;
    }
    else
    {
        cout << "Index : " << index << endl;
    }
    
    return 0;
}

코드는 C++17 이상에서만 컴파일됩니다.

C++14 이하에서도 되는 코드는 아래 링크에 있습니다 ㅎㅎ

https://ideone.com/dKi0sA

알고리즘 자체는 꽤 오래전에 배웠고 이해했었다고 생각했는데 최근에 보니까 또 아닌 것 같더라구요 ㅠㅠ

그래서 다시 공부한 후 자료를 보지 않고 직접 짜봤습니다.

그래서 빼먹은 부분이 있을 수도 있어요 ㅋㅋ...

KMP는 개인적으로 좋아하는 알고리즘이기도 합니다.

원리가 직관적이며 이해하기 쉽고(?) 구현체의 각 부분이나 전체가 활용도가 높기 때문이죠!

질문이 있으시다면 댓글을 주세요!

같이 고민해봅시다!