문자열 검색 알고리즘

개요

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

핵심 용어 정리

용어	설명
텍스트(T)	검색 대상 문자열, 길이 N
패턴(P)	찾으려는 문자열, 길이 M
전처리(Preprocessing)	패턴을 미리 분석해 건너뜀 정보를 계산
완화(Relaxation)	비교 실패 시 패턴을 얼마나 오른쪽으로 이동할지 결정

알고리즘 선택 기준:

• 패턴이 반복 구조를 가지거나 최악 보장이 필요 → KMP
• 자연어 텍스트, 패턴이 길고 알파벳이 큼 → Boyer-Moore-Horspool
• 여러 패턴을 동시에 검색 → Rabin-Karp 또는 Aho-Corasick
• 단순 단일 검색 → std::string::find (이미 최적화됨)

---

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. Z 알고리즘

Z 알고리즘은 문자열 S에서 각 위치 i에 대해 S[i:]가 S 자체와 얼마나 긴 공통 접두사를 가지는지를 O(N) 시간에 계산합니다. 패턴 검색에 응용하면 KMP와 동일한 O(N+M) 성능을 달성합니다.

// Z 배열 계산: z[i] = S[i:]와 S의 최장 공통 접두사 길이
std::vector<int> BuildZArray(std::string_view s)
{
    int n = (int)s.size();
    std::vector<int> z(n, 0);
    z[0] = n; // 관례상 전체 길이

    int l = 0, r = 0; // 현재 Z-box 범위 [l, r)
    for (int i = 1; i < n; ++i)
    {
        if (i < r)
            z[i] = std::min(r - i, z[i - l]);

        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];

        if (i + z[i] > r)
        {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

// Z 알고리즘으로 패턴 검색
// 패턴 P와 텍스트 T를 "P$T" 형태로 합쳐서 Z 배열 계산
std::vector<int> ZSearch(std::string_view text, std::string_view pattern)
{
    std::string combined = std::string(pattern) + "$" + std::string(text);
    auto z = BuildZArray(combined);

    std::vector<int> positions;
    int m = (int)pattern.size();

    for (int i = m + 1; i < (int)combined.size(); ++i)
    {
        if (z[i] == m)
            positions.push_back(i - m - 1); // 텍스트 내 실제 위치
    }
    return positions;
}
// 시간: O(N+M), 공간: O(N+M)

---

6. Aho-Corasick — 다중 패턴 검색

여러 패턴을 동시에 텍스트에서 찾아야 할 때 사용합니다. Trie에 실패 링크(failure link)를 추가하여 KMP를 다중 패턴으로 확장한 알고리즘입니다.

시간복잡도: 전처리 O(총 패턴 길이), 검색 O(N + 출현 횟수)

게임에서 수백 개의 금칙어를 단일 패스로 텍스트에서 탐지할 때 특히 유용합니다.

#include <unordered_map>
#include <queue>

class AhoCorasick
{
    struct AhoNode
    {
        std::unordered_map<char, int> children;
        int fail = 0;           // 실패 링크
        int output = -1;        // 매칭된 패턴 인덱스 (-1: 없음)
    };

    std::vector<AhoNode> _nodes;
    std::vector<std::string> _patterns;

public:
    AhoCorasick() { _nodes.emplace_back(); } // 루트 노드

    void AddPattern(const std::string& pattern)
    {
        int cur = 0;
        for (char c : pattern)
        {
            if (!_nodes[cur].children.count(c))
            {
                _nodes[cur].children[c] = (int)_nodes.size();
                _nodes.emplace_back();
            }
            cur = _nodes[cur].children[c];
        }
        _nodes[cur].output = (int)_patterns.size();
        _patterns.push_back(pattern);
    }

    // BFS로 실패 링크 구축
    void Build()
    {
        std::queue<int> q;
        for (auto& [c, child] : _nodes[0].children)
        {
            _nodes[child].fail = 0;
            q.push(child);
        }

        while (!q.empty())
        {
            int cur = q.front(); q.pop();
            for (auto& [c, child] : _nodes[cur].children)
            {
                int fail = _nodes[cur].fail;
                while (fail && !_nodes[fail].children.count(c))
                    fail = _nodes[fail].fail;
                if (_nodes[fail].children.count(c) && _nodes[fail].children[c] != child)
                    fail = _nodes[fail].children[c];
                _nodes[child].fail = fail;
                q.push(child);
            }
        }
    }

    // 텍스트에서 모든 패턴 매칭 위치 반환: {위치, 패턴 인덱스}
    std::vector<std::pair<int,int>> Search(std::string_view text) const
    {
        std::vector<std::pair<int,int>> results;
        int cur = 0;

        for (int i = 0; i < (int)text.size(); ++i)
        {
            char c = text[i];
            while (cur && !_nodes[cur].children.count(c))
                cur = _nodes[cur].fail;
            if (_nodes[cur].children.count(c))
                cur = _nodes[cur].children.at(c);

            if (_nodes[cur].output != -1)
            {
                int patIdx = _nodes[cur].output;
                int startPos = i - (int)_patterns[patIdx].size() + 1;
                results.push_back({startPos, patIdx});
            }
        }
        return results;
    }
};

// 사용 예시: 금칙어 다중 탐지
void ExampleAhoCorasick()
{
    AhoCorasick ac;
    ac.AddPattern("hack");
    ac.AddPattern("cheat");
    ac.AddPattern("exploit");
    ac.Build();

    std::string chatMessage = "I found an exploit to hack the game";
    auto matches = ac.Search(chatMessage);
    // matches: [(18, 2), (28, 0)] → "exploit"@18, "hack"@28
}

---

7. 알고리즘 비교

알고리즘	전처리	검색 평균	검색 최악	특징
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)	다중 패턴, 롤링 해시
Z 알고리즘	O(N+M)	O(N+M)	O(N+M)	구현 단순, 접두사 분석
Aho-Corasick	O(전체 패턴 합)	O(N+출현수)	O(N+출현수)	다중 패턴 동시 검색

A = 알파벳 크기 (BMH Bad Character Table 크기)

---

8. 게임 개발 활용 사례

8.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 = "안녕, [PLAYER_NAME]! [PLAYER_NAME]님, 환영합니다.";
auto result = ReplaceAll(dialogue, "[PLAYER_NAME]", "알렉스");
// "안녕, 알렉스! 알렉스님, 환영합니다."

8.2 채팅 금칙어 필터 — Aho-Corasick 활용

단일 Brute-Force나 KMP로 금칙어를 검사하면 금칙어 수만큼 패스가 필요하지만, Aho-Corasick은 단일 패스로 모든 금칙어를 동시 탐지합니다.

class ChatProfanityFilter
{
    AhoCorasick _ac;
    bool _built = false;

public:
    void LoadBadWords(const std::vector<std::string>& badWords)
    {
        for (const auto& w : badWords)
            _ac.AddPattern(w);
        _ac.Build();
        _built = true;
    }

    // 금칙어 포함 여부 확인 — O(N + 출현 수)
    bool ContainsProfanity(const std::string& message) const
    {
        if (!_built) return false;
        // 소문자 변환 후 검사 (대소문자 무시)
        std::string lower = message;
        std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);
        return !_ac.Search(lower).empty();
    }

    // 금칙어를 '*'로 대체
    std::string CensorMessage(const std::string& message) const
    {
        if (!_built) return message;
        std::string lower = message;
        std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);

        std::string result = message;
        auto matches = _ac.Search(lower);
        // 뒤에서부터 대체 (인덱스 유지)
        std::sort(matches.rbegin(), matches.rend());
        for (auto [pos, patIdx] : matches)
        {
            int len = (int)lower.size(); // 패턴 길이 필요 시 저장
            (void)pos; (void)len;
            // 실제 구현에서는 패턴 길이를 별도 저장하여 대체
        }
        return result;
    }
};

8.3 콘솔 커맨드 파서

// 게임 콘솔에서 입력된 명령어 파싱
// "god", "noclip", "give item sword 5" 같은 커맨드 처리
class ConsoleCommandParser
{
    std::unordered_map<std::string, std::function<void(std::string_view)>> _handlers;

public:
    void RegisterCommand(const std::string& cmd,
        std::function<void(std::string_view)> handler)
    {
        _handlers[cmd] = handler;
    }

    bool Parse(std::string_view input)
    {
        // 커맨드 이름 추출 (첫 번째 공백까지)
        size_t spacePos = input.find(' ');
        std::string cmdName(input.substr(0, spacePos));
        std::string_view args = spacePos != std::string_view::npos
            ? input.substr(spacePos + 1)
            : std::string_view{};

        auto it = _handlers.find(cmdName);
        if (it != _handlers.end())
        {
            it->second(args);
            return true;
        }
        return false;
    }
};

8.4 게임 로그 빠른 오류 탐색

// 대용량 게임 로그에서 오류 패턴 빠르게 검색 (BMH 활용)
struct FLogSearchResult
{
    int    LineNumber;
    int    Position;
    std::string LineContent;
};

std::vector<FLogSearchResult> SearchGameLog(
    const std::string& logContent, std::string_view errorPattern)
{
    auto positions = BoyerMooreHorspool(logContent, errorPattern);
    std::vector<FLogSearchResult> results;

    for (int pos : positions)
    {
        // 해당 위치의 줄 번호 계산
        int lineNum = 1 + (int)std::count(
            logContent.begin(), logContent.begin() + pos, '\n');

        // 줄 시작과 끝 위치 계산
        size_t lineStart = logContent.rfind('\n', pos);
        lineStart = (lineStart == std::string::npos) ? 0 : lineStart + 1;
        size_t lineEnd = logContent.find('\n', pos);

        results.push_back({
            lineNum,
            pos,
            logContent.substr(lineStart,
                lineEnd == std::string::npos ? std::string::npos : lineEnd - lineStart)
        });
    }
    return results;
}

---

요약

• KMP: 최악에도 O(N+M) 보장. 패턴이 반복 구조를 가질 때 (예: “AAAB” 패턴) 특히 안전하다. 실패 함수(failure function) 이해가 핵심이다.
• Boyer-Moore-Horspool: 평균 O(N/M)로 실전에서 가장 빠르다. 알파벳이 크고 패턴이 긴 자연어 텍스트 검색에 최적이다.
• Rabin-Karp: 롤링 해시로 O(N+M) 평균. 동일 길이 다중 패턴 검색에 유리하다. 큰 소수 mod값으로 해시 충돌을 최소화해야 한다.
• Z 알고리즘: 구현이 단순하고 O(N+M) 보장. 접두사 분석이 필요한 문제에 직관적으로 적용된다.
• Aho-Corasick: 수백 개 금칙어를 단일 패스로 동시 탐지. 게임 채팅 필터, 다중 키워드 스크립트 파싱에 필수적이다.
• std::string::find는 내부적으로 최적화되어 있으므로, 단순 단일 패턴 검색에서는 표준 라이브러리를 우선 사용한다.