문자열 검색 알고리즘

개요

문자열 검색(String Matching)은 텍스트 T에서 패턴 P가 등장하는 위치를 찾는 문제입니다. 단순 브루트포스는 O(N×M)이지만, KMP·Boyer-Moore·Rabin-Karp 알고리즘은 전처리를 통해 O(N+M) 또는 평균 O(N/M)으로 개선합니다. 게임에서는 대화 스크립트 파싱, 로그 분석, 에셋 이름 검색, 프로토콜 파싱에 활용됩니다.

---

1. 브루트포스 (기준선)

#include <string>
#include <vector>

std::vector<int> BruteForce(std::string_view text, std::string_view pattern)
{
    std::vector<int> positions;
    int n = (int)text.size(), m = (int)pattern.size();

    for (int i = 0; i <= n - m; i++)
    {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) j++;
        if (j == m) positions.push_back(i);
    }
    return positions;
}
// 시간: O(N×M), 공간: O(1)

---

2. KMP (Knuth-Morris-Pratt)

패턴 내부의 반복 구조를 분석한 Failure Function(실패 함수)을 사용해 불필요한 비교를 건너뜁니다.

2.1 Failure Function 구축

std::vector<int> BuildFailureFunction(std::string_view pattern)
{
    int m = (int)pattern.size();
    std::vector<int> fail(m, 0);

    for (int i = 1, j = 0; i < m; i++)
    {
        while (j > 0 && pattern[i] != pattern[j])
            j = fail[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        fail[i] = j;
    }
    return fail;
}

2.2 KMP 검색

std::vector<int> KMP(std::string_view text, std::string_view pattern)
{
    std::vector<int> positions;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) return positions;

    auto fail = BuildFailureFunction(pattern);

    for (int i = 0, j = 0; i < n; i++)
    {
        while (j > 0 && text[i] != pattern[j])
            j = fail[j - 1];
        if (text[i] == pattern[j])
            j++;
        if (j == m)
        {
            positions.push_back(i - m + 1);
            j = fail[j - 1]; // 중복 매칭 허용
        }
    }
    return positions;
}
// 시간: O(N+M), 공간: O(M)

---

3. Boyer-Moore-Horspool

패턴을 오른쪽에서 왼쪽으로 비교하고, Bad Character Table로 최대 이동 거리를 계산합니다. 실제 텍스트 검색에서 평균적으로 가장 빠른 알고리즘 중 하나입니다.

#include <array>

std::vector<int> BoyerMooreHorspool(
    std::string_view text, std::string_view pattern)
{
    std::vector<int> positions;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0 || m > n) return positions;

    // Bad Character Table: 각 문자의 마지막 등장 위치
    std::array<int, 256> skip{};
    skip.fill(m);
    for (int i = 0; i < m - 1; i++)
        skip[(unsigned char)pattern[i]] = m - 1 - i;

    int i = m - 1;
    while (i < n)
    {
        int j = m - 1, k = i;
        while (j >= 0 && text[k] == pattern[j])
        {
            j--; k--;
        }
        if (j < 0)
            positions.push_back(k + 1);

        i += skip[(unsigned char)text[i]];
    }
    return positions;
}
// 평균: O(N/M), 최악: O(N×M) (반복 패턴에서)

---

4. Rabin-Karp (해시 기반)

패턴의 해시값을 계산하고, 텍스트의 슬라이딩 윈도우 해시와 비교합니다. 다중 패턴 검색에 특히 유용합니다.

std::vector<int> RabinKarp(
    std::string_view text, std::string_view pattern,
    long long base = 31, long long mod = 1'000'000'007LL)
{
    std::vector<int> positions;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m > n) return positions;

    // 패턴 해시 계산
    long long patHash = 0, winHash = 0, power = 1;
    for (int i = 0; i < m - 1; i++) power = power * base % mod;
    for (int i = 0; i < m; i++)
    {
        patHash = (patHash * base + pattern[i]) % mod;
        winHash = (winHash * base + text[i])   % mod;
    }

    for (int i = 0; i <= n - m; i++)
    {
        if (winHash == patHash)
        {
            // 해시 충돌 검증
            if (text.substr(i, m) == pattern)
                positions.push_back(i);
        }
        if (i < n - m)
        {
            // 롤링 해시 업데이트
            winHash = (winHash - text[i] * power % mod + mod) % mod;
            winHash = (winHash * base + text[i + m]) % mod;
        }
    }
    return positions;
}
// 평균: O(N+M), 최악: O(N×M) (해시 충돌 시)

---

5. 알고리즘 비교

알고리즘	전처리	검색 평균	검색 최악	특징
Brute Force	O(1)	O(N×M)	O(N×M)	단순, 짧은 텍스트
KMP	O(M)	O(N+M)	O(N+M)	최악 보장, 중복 매칭
BMH	O(M+A)	O(N/M)	O(N×M)	실전 가장 빠름
Rabin-Karp	O(M)	O(N+M)	O(N×M)	다중 패턴에 유리

---

6. 게임 개발 활용 사례

6.1 대화 스크립트 키워드 감지

// NPC 대화에서 플레이어 이름 치환
std::string ReplaceAll(std::string text,
    std::string_view pattern, std::string_view replacement)
{
    auto positions = KMP(text, pattern);
    // 뒤에서부터 치환해야 인덱스가 유지됨
    for (int i = (int)positions.size() - 1; i >= 0; i--)
    {
        text.replace(positions[i], pattern.size(), replacement);
    }
    return text;
}

std::string dialogue = "Hello, [PLAYER_NAME]! Welcome, [PLAYER_NAME].";
auto result = ReplaceAll(dialogue, "[PLAYER_NAME]", "Alice");
// "Hello, Alice! Welcome, Alice."

6.2 로그 파일 빠른 검색

// 게임 로그에서 오류 패턴 빠르게 찾기
void SearchLog(const std::string& logContent)
{
    static const std::string errorPattern = "[ERROR]";
    auto positions = BoyerMooreHorspool(logContent, errorPattern);

    for (int pos : positions)
    {
        // 해당 줄의 끝까지 추출
        size_t lineEnd = logContent.find('\n', pos);
        std::string line = logContent.substr(pos,
            lineEnd == std::string::npos ? std::string::npos : lineEnd - pos);
        std::cerr << line << '\n';
    }
}

---

요약

• KMP는 최악의 경우에도 O(N+M)을 보장하므로 패턴이 반복 구조를 가질 때 안전하다.
• Boyer-Moore-Horspool은 평균적으로 가장 빠르며, 알파벳이 크고 패턴이 긴 자연어 텍스트 검색에 적합하다.
• Rabin-Karp는 다중 패턴을 동시에 찾을 때 유리하다. 해시 충돌 방지를 위해 큰 소수 mod값을 사용한다.
• std::string::find는 내부적으로 최적화된 알고리즘을 사용하므로, 단순 단일 패턴 검색에서는 표준 라이브러리를 먼저 활용한다.