C++ 문자열 패턴 매칭: KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열

들어가며: 단순 검색이 느려지는 조건

텍스트 길이를 n, 패턴 길이를 m이라고 하면 단순 검색은 최악의 경우 위치마다 패턴 전체를 비교해 n×m번 비교합니다. n이 100만, m이 100이면 최대 1억 번입니다. 다만 실제 텍스트에서는 첫 몇 글자에서 불일치가 나서 바로 다음 위치로 넘어가는 경우가 대부분이라, 최악에 가까워지는 것은 "aaaa...ab" 같은 반복이 많은 입력입니다. KMP는 텍스트 포인터를 뒤로 되돌리지 않아 어떤 입력에서도 O(n+m)을 보장하고, Boyer-Moore는 패턴을 오른쪽부터 비교해 불일치가 나면 여러 칸을 건너뜁니다.

---

단순 검색이 느려지는 문자열 처리 상황

대용량 로그에서 에러 패턴 검색

상황: 100MB 로그 파일에서 "FATAL: connection timeout" 패턴이 등장하는 모든 위치를 찾아야 합니다. 잘못된 접근: 주요 표준 라이브러리의 std::string::find는 첫 글자를 memchr 등으로 찾은 뒤 나머지를 비교하는 방식이라 보통은 빠르지만, 최악의 입력에서는 O(n×m)이 될 수 있습니다. 해결: KMP 또는 Boyer-Moore. KMP는 O(n+m)을 보장하고, Boyer-Moore는 실무 텍스트에서 평균적으로 더 빠릅니다. C++17부터는 std::search에 std::boyer_moore_searcher나 std::boyer_moore_horspool_searcher를 넘겨 직접 구현 없이 쓸 수 있습니다.

---

DNA 서열에서 유사 구간 탐색

상황: 두 DNA 서열(수만 bp)에서 동일한 부분 문자열을 찾아야 합니다. 잘못된 접근: 모든 부분 문자열을 나열해 비교하면 O(n² × m) 수준입니다. 해결: 접미사 배열 또는 해시(Rabin-Karp). 접미사 배열로 O(n log n) 구축 후 이진 탐색으로 O(m log n)에 검색 가능합니다.

---

표절 검사 - 문서 유사도

상황: 두 문서에서 “연속된 k글자”가 얼마나 겹치는지 계산해 유사도를 판단해야 합니다. 잘못된 접근: 모든 k-gram을 나열해 비교하면 메모리와 시간이 폭발합니다. 해결: Rabin-Karp 해시. 각 문서의 k-gram 해시를 O(n)에 계산하며, 해시 집합으로 교집합을 구합니다.

---

에디터 “찾기” 기능

상황: 수천 줄의 소스 코드에서 사용자가 입력한 검색어를 실시간으로 하이라이트해야 합니다. 잘못된 접근: 매번 전체 텍스트를 다시 스캔하면 타이핑할 때마다 지연이 발생합니다. 해결: Boyer-Moore (패턴이 길 때) 또는 KMP (빠른 구현). 짧은 패턴은 단순 검색도 충분합니다.

---

문자열 내 모든 회문 찾기

상황: 문자열에서 모든 회문(앞뒤가 같은 부분)의 개수 또는 최장 회문을 구해야 합니다. 잘못된 접근: 각 위치를 중심으로 확장하면 O(n²)인데, Manacher 알고리즘 없이는 짝수 길이 회문 처리가 까다롭습니다. 해결: Manacher 알고리즘 O(n) 또는 Z 알고리즘을 활용한 회문 판별.

---

네트워크 DPI·패킷 패턴 매칭

상황: 실시간 패킷 스트림에서 악성 시그니처(예: "GET /admin", 바이너리 시퀀스)가 포함된 패킷을 검출해야 합니다. 잘못된 접근: 패킷 전체를 메모리에 버퍼링한 뒤 단순 검색하면 지연과 메모리 부담이 큽니다. 해결: 시그니처가 하나라면 KMP처럼 상태(현재 일치 길이)만 들고 다니며 스트리밍 검색을 하고, 시그니처가 수백·수천 개라면 여러 패턴을 한 번에 찾는 Aho-Corasick 오토마톤을 씁니다. 청크 단위로 처리할 때는 경계에 걸친 패턴을 놓치지 않도록 상태를 이어 가거나 오버랩을 둡니다.

---

검색 엔진 자동완성·접두사 검색

상황: 수천 개의 키워드에서 사용자 입력과 일치하는 접두사를 가진 항목을 빠르게 찾아야 합니다. 잘못된 접근: 모든 키워드를 순회하며 strncmp하면 O(키워드 수 × 입력 길이)입니다. 해결: 키워드를 정렬해 두고 lower_bound로 입력이 접두사인 구간을 이진 탐색하거나(O(m log k), k는 키워드 수), 트라이(Trie)로 입력 길이 m에 비례하는 시간에 찾습니다. 접미사 배열은 키워드의 “중간”에 있는 부분 문자열까지 찾아야 할 때 씁니다.

---

알고리즘 선택 가이드

문제 유형	추천 알고리즘	시간 복잡도
단일 패턴 매칭 (일반)	KMP	O(n + m)
단일 패턴 (실무 검색)	Boyer-Moore	O(n) 평균, O(n×m) 최악
다중 패턴 (같은 길이, 해시 기반)	Rabin-Karp	O(n + 전체 패턴 길이) 평균
다중 패턴 (길이 무관, 대량)	Aho-Corasick	O(n + 전체 패턴 길이 + 매칭 수)
접두사-접미사 일치	Z 알고리즘	O(n)
부분 문자열 검색, LCP	접미사 배열	O(n log n) 구축, O(m log n) 검색

---

패턴 매칭 문제 정의와 복잡도

문제 정의

패턴 매칭: 텍스트 T(길이 n)에서 패턴 P(길이 m)가 등장하는 모든 시작 위치를 찾는 문제.

flowchart LR
  subgraph T[텍스트 T]
    T1[a] --> T2[b] --> T3[c] --> T4[a] --> T5[b] --> T6[c] --> T7[a]
  end
  subgraph P[패턴 P]
    P1[a] --> P2[b] --> P3[c]
  end
  T4 -.-> P1
  T5 -.-> P2
  T6 -.-> P3

단순 검색 (브루트포스):

// ❌ O(n×m) - 매 위치에서 패턴 전체 비교
std::vector<int> naive_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m > n) return positions;
    for (int i = 0; i <= n - m; ++i) {
        bool found = true;
        for (int j = 0; j < m; ++j) {
            if (text[i + j] != pattern[j]) {
                found = false;
                break;
            }
        }
        if (found) positions.push_back(i);
    }
    return positions;
}

---

KMP 알고리즘

핵심 아이디어

KMP는 실패 함수(failure function)를 이용해, 불일치가 나면 이미 일치한 부분 중 다시 쓸 수 있는 접두사 길이로 패턴 위치를 옮깁니다. 텍스트 포인터는 절대 뒤로 가지 않습니다. 한 번의 불일치에서 lps를 여러 번 따라갈 수는 있지만, 따라갈 때마다 j가 줄어들고 j는 텍스트를 읽을 때만 1씩 늘어나므로 전체 비교 횟수는 2n을 넘지 않습니다.

flowchart TD
  A[텍스트 위치 i, 패턴 위치 j] --> B{일치?}
  B -->|Yes| C[j++]
  B -->|No| D["j = lps[j-1]"]
  C --> E{j == m?}
  E -->|Yes| F[매칭 발견]
  E -->|No| A
  D --> G{j > 0?}
  G -->|Yes| A
  G -->|No| H[i++]
  H --> A

실패 함수 (LPS) 구축

lps[i] = pattern[0..i]의 진접미사이면서 진접두사인 최대 길이. 예: pattern = "ABABCABAB" → lps = [0,0,1,2,0,1,2,3,4]

• lps[2]=1: “ABA”에서 “A”가 접두사이자 접미사
• lps[3]=2: “ABAB”에서 “AB”가 접두사이자 접미사

#include <vector>
#include <string>
// LPS(Longest Proper Prefix which is also Suffix) 배열 구축
// lps[i] = pattern[0..i]에서 접두사=접미사인 최대 길이 (자기 자신 제외)
// 시간: O(m)
std::vector<int> build_lps(const std::string& pattern) {
    int m = static_cast<int>(pattern.size());
    std::vector<int> lps(m, 0);
    int len = 0;  // 이전까지 일치한 길이
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            ++len;
            lps[i] = len;
            ++i;
        } else {
            if (len != 0) {
                len = lps[len - 1];  // 이전 lps로 되돌아가기
            } else {
                lps[i] = 0;
                ++i;
            }
        }
    }
    return lps;
}

완전한 KMP 구현

// KMP 패턴 매칭
// 시간: O(n + m), 공간: O(m)
std::vector<int> kmp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m > n || m == 0) return positions;
    std::vector<int> lps = build_lps(pattern);
    int i = 0;  // 텍스트 인덱스
    int j = 0;  // 패턴 인덱스
    while (i < n) {
        if (text[i] == pattern[j]) {
            ++i;
            ++j;
        }
        if (j == m) {
            positions.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                ++i;
            }
        }
    }
    return positions;
}

KMP 활용: 문자열 반복 주기

// 문자열이 더 짧은 패턴의 반복으로 이루어졌는지 판별
// "abcabcabc" -> true (주기 3인 "abc"의 3회 반복), "abcab" -> false
bool is_repeated(const std::string& s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return false;
    std::vector<int> lps = build_lps(s);
    int period = n - lps[n - 1];
    return (n % period == 0 && period < n);
}

---

Rabin-Karp 알고리즘

핵심 아이디어

롤링 해시: 윈도우를 한 칸 옮길 때, 맨 앞 문자를 빼고 맨 뒤에 새 문자를 더하는 방식으로 해시를 O(1)에 갱신합니다. 해시가 같으면 추가로 문자별 비교(충돌 처리).

flowchart LR
  A["해시(T[i..i+m-1])"] --> B{"해시 == 해시(P)?"}
  B -->|No| C[다음 위치]
  B -->|Yes| D[문자별 검증]
  D --> E{실제 일치?}
  E -->|Yes| F[매칭 발견]
  E -->|No| G[해시 충돌]
  C --> A

완전한 Rabin-Karp 구현

#include <vector>
#include <string>
// Rabin-Karp: 롤링 해시 기반 패턴 매칭
// base=256, mod=큰 소수. 충돌 시 문자별 검증.
// char가 signed인 플랫폼에서 한글 같은 바이트(0x80 이상)가 음수가 되지 않도록 unsigned char로 변환
// 시간: O(n+m) 평균, O(n×m) 최악(모든 위치에서 충돌)
std::vector<int> rabin_karp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m > n || m == 0) return positions;
    const int base = 256;
    const int mod = 1000000007;  // 큰 소수
    // base^(m-1) % mod (윈도우 이동 시 맨 앞 문자 제거용)
    int h = 1;
    for (int i = 0; i < m - 1; ++i) {
        h = (static_cast<long long>(h) * base) % mod;
    }
    // 패턴 해시
    int pattern_hash = 0;
    for (int i = 0; i < m; ++i) {
        pattern_hash = (static_cast<long long>(pattern_hash) * base + static_cast<unsigned char>(pattern[i])) % mod;
    }
    // 첫 윈도우 해시
    int window_hash = 0;
    for (int i = 0; i < m; ++i) {
        window_hash = (static_cast<long long>(window_hash) * base + static_cast<unsigned char>(text[i])) % mod;
    }
    for (int i = 0; i <= n - m; ++i) {
        if (window_hash == pattern_hash) {
            // 해시 충돌 가능성 있음 - 문자별 검증
            bool match = true;
            for (int j = 0; j < m; ++j) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) positions.push_back(i);
        }
        if (i < n - m) {
            // 롤링: 맨 앞 제거, 맨 뒤 추가
            window_hash = (window_hash - static_cast<long long>(static_cast<unsigned char>(text[i])) * h % mod + mod) % mod;
            window_hash = (static_cast<long long>(window_hash) * base + static_cast<unsigned char>(text[i + m])) % mod;
        }
    }
    return positions;
}

표절 검사: k-gram 해시 (Rabin-Karp 활용)

두 문서의 유사도를 k-gram(연속 k글자) 해시 교집합으로 계산합니다.

#include <unordered_set>
// 문서에서 k-gram 해시 집합 추출. O(n)
std::unordered_set<int> extract_kgram_hashes(const std::string& doc, int k) {
    std::unordered_set<int> hashes;
    const int base = 256, mod = 1000000007;
    int n = static_cast<int>(doc.size());
    if (n < k) return hashes;
    int h = 1;
    for (int i = 0; i < k - 1; ++i)
        h = (static_cast<long long>(h) * base) % mod;
    int window = 0;
    for (int i = 0; i < k; ++i)
        window = (static_cast<long long>(window) * base + static_cast<unsigned char>(doc[i])) % mod;
    hashes.insert(window);
    for (int i = k; i < n; ++i) {
        window = (window - static_cast<long long>(static_cast<unsigned char>(doc[i - k])) * h % mod + mod) % mod;
        window = (static_cast<long long>(window) * base + static_cast<unsigned char>(doc[i])) % mod;
        hashes.insert(window);
    }
    return hashes;
}
// Jaccard 유사도: |교집합| / |합집합| (해시 충돌이 있으면 약간 과대평가될 수 있음)
double jaccard_similarity(const std::unordered_set<int>& a,
                          const std::unordered_set<int>& b) {
    int inter = 0;
    for (int h : a) if (b.count(h)) ++inter;
    int uni = static_cast<int>(a.size() + b.size() - inter);
    return uni == 0 ? 0.0 : static_cast<double>(inter) / uni;
}

다중 패턴 검색 (Rabin-Karp 확장)

#include <unordered_map>
// 동일 길이 패턴 여러 개를 한 번의 스캔으로 검색 - 해시 맵 활용
// 패턴 길이가 다르면 길이별로 그룹화해 각각 스캔
std::vector<std::pair<int, std::string>> rabin_karp_multi_same_length(
    const std::string& text,
    const std::vector<std::string>& patterns)
{
    std::vector<std::pair<int, std::string>> results;
    if (patterns.empty()) return results;
    int m = static_cast<int>(patterns[0].size());
    for (const auto& p : patterns) {
        if (static_cast<int>(p.size()) != m) return {};  // 길이 다르면 단순화
    }
    std::unordered_map<int, std::vector<std::string>> hash_to_patterns;
    const int base = 256, mod = 1000000007;
    for (const auto& p : patterns) {
        int h = 0;
        for (char c : p) h = (static_cast<long long>(h) * base + static_cast<unsigned char>(c)) % mod;
        hash_to_patterns[h].push_back(p);
    }
    int n = static_cast<int>(text.size());
    if (m == 0 || m > n) return results;
    int h = 1;
    for (int i = 0; i < m - 1; ++i) h = (static_cast<long long>(h) * base) % mod;
    int window_hash = 0;
    for (int i = 0; i < m; ++i) {
        window_hash = (static_cast<long long>(window_hash) * base + static_cast<unsigned char>(text[i])) % mod;
    }
    for (int i = 0; i <= n - m; ++i) {
        auto it = hash_to_patterns.find(window_hash);
        if (it != hash_to_patterns.end()) {
            for (const auto& p : it->second) {
                bool match = true;
                for (int j = 0; j < m; ++j) {
                    if (text[i + j] != p[j]) { match = false; break; }
                }
                if (match) results.emplace_back(i, p);
            }
        }
        if (i < n - m) {
            window_hash = (window_hash - static_cast<long long>(static_cast<unsigned char>(text[i])) * h % mod + mod) % mod;
            window_hash = (static_cast<long long>(window_hash) * base + static_cast<unsigned char>(text[i + m])) % mod;
        }
    }
    return results;
}

---

Boyer-Moore 알고리즘

핵심 아이디어

패턴을 오른쪽부터 왼쪽으로 비교합니다. 불일치 시 Bad Character와 Good Suffix 휴리스틱으로 여러 칸을 한 번에 건너뜁니다. 알파벳이 크고 패턴이 긴 자연어 텍스트에서는 비교 횟수가 평균적으로 n/m에 가까워져, 텍스트의 모든 글자를 보지 않고 끝나기도 합니다.

flowchart TD
  A[오른쪽부터 비교] --> B{불일치}
  B --> C[Bad Character: 불일치한 텍스트 문자를 패턴의 마지막 같은 문자에 맞추도록 이동]
  B --> D[Good Suffix: 일치한 접미사가 패턴 앞에 있으면 그 위치로]
  C --> E[최대 점프량 선택]
  D --> E
  E --> A

Bad Character 테이블

#include <vector>
#include <string>
#include <algorithm>
// Bad Character: pattern에서 각 문자의 마지막 등장 위치
// 불일치 시 text의 문자를 패턴 오른쪽에 맞추기 위해 점프
std::vector<int> build_bad_char(const std::string& pattern) {
    const int ALPHABET = 256;
    std::vector<int> bad_char(ALPHABET, -1);
    for (int i = 0; i < static_cast<int>(pattern.size()); ++i) {
        bad_char[static_cast<unsigned char>(pattern[i])] = i;
    }
    return bad_char;
}

완전한 Boyer-Moore 구현 (Bad Character만)

// Boyer-Moore (Bad Character 휴리스틱만 - 구현 간소화)
// Good Suffix까지 쓰면 더 빠르지만 구현이 복잡
// 시간: O(n) 평균, O(n×m) 최악
std::vector<int> boyer_moore_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m > n || m == 0) return positions;
    std::vector<int> bad_char = build_bad_char(pattern);
    int s = 0;  // shift (텍스트에서 패턴 시작 위치)
    while (s <= n - m) {
        int j = m - 1;
        while (j >= 0 && text[s + j] == pattern[j]) --j;
        if (j < 0) {
            positions.push_back(s);
            s += (s + m < n) ? m - bad_char[static_cast<unsigned char>(text[s + m])] : 1;
        } else {
            int bc_shift = j - bad_char[static_cast<unsigned char>(text[s + j])];
            s += std::max(1, bc_shift);
        }
    }
    return positions;
}

---

Z 알고리즘

핵심 아이디어

Z[i] = s[0..]와 s[i..]의 최대 공통 접두사 길이. 이를 이용해 패턴 매칭, 회문, 문자열 압축 등에 활용합니다.

flowchart LR
  A["s = P$T"] --> B[Z 배열 구축]
  B --> C["Z[i] = m 이면 T[i-m..]에서 P 매칭"]

Z 배열 구축

// Z 배열: z[i] = s와 s[i..]의 최대 공통 접두사 길이
// 시간: O(n)
std::vector<int> build_z(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) {
            z[i] = std::min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

Z 알고리즘으로 패턴 매칭

s = pattern + '$' + text로 이어붙인 뒤, Z 배열에서 Z[i] == m인 위치가 패턴의 시작 인덱스입니다.

Z 알고리즘 활용: 접두사 일치 개수

문자열의 각 위치에서 전체 문자열과 일치하는 접두사 길이를 O(n)에 구합니다.

// s의 각 위치 i에서 s[0..]와 s[i..]의 최대 공통 접두사 길이
// 활용: 문자열 압축, 반복 패턴 탐지
std::vector<int> z_values = build_z(s);
// i + z_values[i] == n 이면 s는 주기 i를 가짐 (s[k] == s[k+i])
// 여기에 n % i == 0까지 성립하면 s는 s[0..i-1]의 반복

// s = pattern + '$' + text 로 이어붙인 뒤 Z 배열에서 Z[i]=m인 위치
// '$'는 pattern과 text에 등장하지 않는 구분자
std::vector<int> z_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions;
    int m = static_cast<int>(pattern.size());
    int n = static_cast<int>(text.size());
    if (m > n || m == 0) return positions;
    std::string s = pattern + '$' + text;
    std::vector<int> z = build_z(s);
    // s = pattern + '$' + text 이므로 인덱스 m+1 ~ m+n이 text의 시작 위치
    for (int i = m + 1; i <= m + n; ++i) {
        if (z[i] == m) {
            positions.push_back(i - m - 1);
        }
    }
    return positions;
}

---

접미사 배열과 LCP

핵심 아이디어

접미사 배열: 문자열의 모든 접미사를 사전순으로 정렬했을 때의 시작 인덱스 배열. LCP(Longest Common Prefix)와 함께 부분 문자열 검색, LCS 등에 활용합니다.

접미사 배열 구축 (단순 정렬)

#include <vector>
#include <string>
#include <algorithm>
// 접미사 배열 - O(n² log n) 단순 정렬 (교육용)
// 실무에서는 SA-IS 등 O(n) 알고리즘 사용
std::vector<int> build_suffix_array_simple(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> sa(n);
    for (int i = 0; i < n; ++i) sa[i] = i;
    std::sort(sa.begin(), sa.end(), [&s](int a, int b) {
        return s.substr(a) < s.substr(b);
    });
    return sa;
}

접미사 배열 + 이진 탐색으로 패턴 검색

// 접미사 배열에서 패턴이 등장하는 범위 [lo, hi]를 이진 탐색
// 시간: O(m log n)
std::pair<int, int> search_suffix_array(
    const std::string& text,
    const std::vector<int>& sa,
    const std::string& pattern)
{
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    auto cmp = [&](int idx, const std::string& p) {
        return text.compare(idx, std::min(n - idx, static_cast<int>(p.size())), p) < 0;
    };
    int lo = std::lower_bound(sa.begin(), sa.end(), pattern, cmp) - sa.begin();
    int hi = lo;
    while (hi < n && text.compare(sa[hi], std::min(n - sa[hi], m), pattern) == 0) ++hi;
    return {lo, hi - 1};
}

LCP 배열과 최장 반복 부분 문자열

접미사 배열과 LCP 배열이 있으면 최장 반복 부분 문자열(Longest Repeated Substring)은 LCP 최댓값을 한 번 훑는 O(n)으로 구할 수 있습니다. 전체 비용은 접미사 배열 구축이 좌우합니다. build_lcp는 바로 아래에 정의되어 있으므로 실제 코드에서는 먼저 선언해야 합니다.

// LCP[i] = sa[i]와 sa[i-1] 접미사의 최대 공통 접두사 길이
// 최장 반복 부분 문자열 = max(LCP[i])에 해당하는 구간
std::string longest_repeated_substring(const std::string& s) {
    auto sa = build_suffix_array_simple(s);
    auto lcp = build_lcp(s, sa);
    int n = static_cast<int>(s.size());
    int max_len = 0, start = 0;
    for (int i = 1; i < n; ++i) {
        if (lcp[i] > max_len) {
            max_len = lcp[i];
            start = sa[i];
        }
    }
    return max_len > 0 ? s.substr(start, max_len) : "";
}

LCP 배열 구축 (선택)

// LCP[i] = sa[i]와 sa[i-1] 접미사의 최대 공통 접두사 길이
std::vector<int> build_lcp(const std::string& s, const std::vector<int>& sa) {
    int n = static_cast<int>(s.size());
    std::vector<int> rank(n), lcp(n);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; ++i) {
        if (rank[i] == 0) { h = 0; continue; }
        int j = sa[rank[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[rank[i]] = h;
        if (h > 0) --h;
    }
    return lcp;
}

---

LPS 인덱스·해시 오버플로우·빈 패턴 처리 버그

KMP LPS 인덱스 오류

증상: lps[j-1] 접근 시 j=0에서 j-1이 -1이 되어 크래시. 원인: j가 0일 때 lps[j-1]을 참조합니다. 해결: j != 0 체크 후에만 j = lps[j-1] 수행.

// ❌ j가 0일 때 lps[-1] 접근
if (text[i] != pattern[j]) {
    j = lps[j - 1];  // j==0이면 오류
}
// ✅
if (text[i] != pattern[j]) {
    if (j != 0) {
        j = lps[j - 1];
    } else {
        ++i;
    }
}

---

Rabin-Karp 해시 오버플로우

증상: 해시 값이 음수가 되거나 잘못된 매칭이 발생합니다. 원인: int 곱셈/덧셈 시 오버플로우. (a - b) % mod에서 a < b면 음수. 해결: long long으로 중간 계산, (x % mod + mod) % mod로 음수 방지.

// ❌ int 오버플로우
window_hash = (window_hash - text[i] * h) % mod;
// ✅
window_hash = (window_hash - static_cast<long long>(text[i]) * h % mod + mod) % mod;

---

Boyer-Moore Bad Character 인덱스

증상: text[s + m] 접근 시 s + m >= n이면 범위 초과. 원인: 마지막 매칭 발견 후 다음 shift 계산 시 s + m이 n을 넘을 수 있습니다. 해결: s + m < n 조건 확인.

// ❌
s += m - bad_char[text[s + m]];  // s+m >= n 가능
// ✅
s += (s + m < n) ? m - bad_char[static_cast<unsigned char>(text[s + m])] : 1;

---

Z 알고리즘 구분자 누락

증상: 반복이 많은 입력에서 매칭 일부가 누락됩니다. 원인: pattern + text만 이어붙이면 Z값이 패턴 경계를 넘어 계속 늘어나 m보다 커질 수 있습니다. 그러면 Z[i] == m 검사에 걸리지 않아 실제 매칭을 놓치고, >= m으로 바꾸면 이번에는 패턴 영역 안에서 시작하는 가짜 매칭이 섞입니다. 해결: pattern + '$' + text처럼 패턴과 텍스트에 없는 구분자를 삽입합니다.

// ❌ text="aaa", pattern="aa" -> s="aaaaa", Z=[_,4,3,2,1]이라 Z==2인 위치가 하나뿐
std::string s = pattern + text;
// ✅
std::string s = pattern + '$' + text;

---

빈 패턴 처리 누락

증상: pattern이 빈 문자열일 때 무한 루프 또는 크래시. 원인: m == 0이면 lps가 비어 있으며, 루프 조건이 잘못될 수 있습니다. 해결: 함수 시작 시 if (m == 0) return positions; 체크.

// ✅ 모든 검색 함수 상단에
if (m > n || m == 0) return positions;

---

unsigned char 변환 누락

증상: 한글 등 비ASCII 문자가 있을 때 bad_char[c]가 범위 밖을 읽어 크래시하거나 잘못된 점프를 합니다. 원인: char가 signed인 플랫폼(x86의 GCC·MSVC 등)에서는 0x800xFF 바이트가 -128-1로 해석되어 음수 인덱스가 됩니다. 해결: static_cast<unsigned char>(c)로 0~255 범위 보장.

// ❌
bad_char[pattern[i]] = i;
// ✅
bad_char[static_cast<unsigned char>(pattern[i])] = i;

---

접미사 배열 정렬 비교자 오류

증상: std::sort의 비교자에서 s.substr(a)를 사용하면 O(n) 비교 × O(n log n) 정렬로 O(n² log n)이 됩니다. 대용량에서 매우 느립니다. 원인: substr은 매번 새 문자열을 생성합니다. 해결: s.compare(a, n - a, s, b, n - b)처럼 인덱스로 비교하면 복사와 할당은 사라집니다. 다만 비교 한 번이 여전히 최악 O(n)이라(예: “aaaa…”) 점근 복잡도는 같습니다. 큰 입력에는 Doubling 기법(O(n log² n), 기수 정렬을 쓰면 O(n log n))이나 SA-IS를 씁니다.

// ❌ O(n² log n) - substr이 매번 복사
std::sort(sa.begin(), sa.end(), [&s](int a, int b) {
    return s.substr(a) < s.substr(b);
});
// ✅ 복사 없는 비교 (점근 복잡도 개선은 Doubling·SA-IS로)
std::sort(sa.begin(), sa.end(), [&s, n](int a, int b) {
    return s.compare(a, n - a, s, b, n - b) < 0;
});

---

Rabin-Karp base·mod 선택 오류

증상: base=10, mod=1000처럼 작은 값을 쓰면 해시 충돌이 빈번해져, 거의 모든 위치에서 문자별 검증이 발생합니다. O(n×m)으로 퇴화합니다. 원인: 해시 공간이 너무 작아 충돌 확률이 높습니다. 해결: base ≥ 256(문자 코드 범위), mod는 10⁹ 이상의 큰 소수. Double hashing으로 충돌 확률을 더 낮출 수 있습니다.

// ❌ base=10, mod=1000 → 충돌 다발
// ✅ base=256, mod=1000000007
const int base = 256;
const int mod = 1000000007;

---

알고리즘 선택 기준과 경계 조건·유니코드 처리

알고리즘 선택 기준

상황	권장 알고리즘	이유
짧은 패턴, 일반 텍스트	std::string::find	테이블 구축 비용이 이득보다 큼, 라이브러리 구현이 이미 최적화됨
긴 패턴, 큰 텍스트	Boyer-Moore(std::boyer_moore_searcher)	불일치 시 큰 점프
최악의 경우도 보장해야 함, 스트리밍	KMP	O(n+m) 보장, 텍스트를 한 방향으로만 읽음
다중 패턴	Rabin-Karp(같은 길이) 또는 Aho-Corasick	한 번 스캔으로 여러 패턴 검색
접두사/접미사 분석	Z 알고리즘	O(n) 선형 시간
같은 텍스트에 반복 검색	접미사 배열	구축 후 질의마다 O(m log n)

어느 길이부터 Boyer-Moore가 이득인지는 알파벳 크기와 구현에 따라 다르므로, 경계가 중요하다면 실제 데이터로 측정해 정합니다.

경계 조건 일관 처리

모든 검색 함수는 동일한 경계 체크를 상단에 두는 것이 좋습니다.

// ✅ 통일된 경계 처리
if (pattern.empty()) return {};
if (static_cast<int>(pattern.size()) > static_cast<int>(text.size())) return {};

테스트 케이스 필수 항목

// 반드시 검증할 케이스
// 1. 빈 패턴
// 2. 패턴 == 텍스트
// 3. 패턴이 텍스트보다 긺
// 4. 단일 문자 패턴
// 5. 반복 패턴 (예: "aaaa" in "aaaaaaaa")
// 6. 매칭 없음
// 7. 여러 매칭 (겹침 포함)

유니코드·멀티바이트 주의

// ⚠️ std::string은 바이트 시퀀스. UTF-8 한글은 여러 바이트.
// "가" = 3바이트. 패턴 매칭은 바이트 단위로 동작.
// 그래픽 단위(글자) 검색이 필요하면 ICU 등 라이브러리 사용.

UTF-8은 글자의 첫 바이트와 이어지는 바이트의 비트 패턴이 달라서, 올바른 UTF-8 패턴을 올바른 UTF-8 텍스트에서 바이트 단위로 찾으면 글자 중간에서 시작하는 가짜 매칭은 생기지 않습니다. 다만 반환되는 위치는 글자 인덱스가 아니라 바이트 오프셋이고, 대소문자 무시나 정규화(NFC/NFD) 차이는 바이트 비교로 처리할 수 없습니다.

---

모듈러 선택·사전 필터·메모리 줄이기

Rabin-Karp 모듈러 선택

// 충돌 확률을 더 낮추려면 2^61-1(메르센 소수)을 mod로 쓴다.
// 이때 두 값의 곱은 64비트를 넘으므로 unsigned __int128(GCC/Clang)이나
// 메르센 소수 전용 곱셈 기법으로 계산해야 한다.
const uint64_t mod = (1ULL << 61) - 1;
// 또는 서로 다른 mod 두 개로 해시를 두 번 계산(double hashing)

접미사 배열 O(n) 구축

std::sort 대신 SA-IS(Suffix Array Induced Sorting)를 사용하면 O(n)에 구축 가능합니다. 라이브러리로는 libsais, divsufsort, sdsl-lite 등이 있습니다.

메모리 최적화

• KMP: lps만 O(m) 유지.
• Rabin-Karp: 해시값만 유지, 윈도우 문자열 저장 불필요.
• 접미사 배열: O(n) 추가 공간.

---

검색 엔진 래퍼와 대용량 파일 스트리밍 검색

검색 엔진 래퍼

#include <string>
#include <vector>
#include <functional>
enum class SearchAlgo { Naive, KMP, RabinKarp, BoyerMoore, Z };
std::vector<int> search(
    const std::string& text,
    const std::string& pattern,
    SearchAlgo algo = SearchAlgo::KMP)
{
    switch (algo) {
        case SearchAlgo::KMP:        return kmp_search(text, pattern);
        case SearchAlgo::RabinKarp:  return rabin_karp_search(text, pattern);
        case SearchAlgo::BoyerMoore: return boyer_moore_search(text, pattern);
        case SearchAlgo::Z:          return z_search(text, pattern);
        default:                     return naive_search(text, pattern);
    }
}

대용량 파일 스트리밍 검색

// 파일을 1MB 청크로 읽어가며 KMP 적용
// 이전 버퍼의 마지막 m-1바이트를 남겨 두면 청크 경계에 걸친 매칭도 찾을 수 있다.
// 남겨 둔 m-1바이트에서 시작하는 매칭은 이전 버퍼에서 완성될 수 없었으므로 중복 보고되지 않는다.
#include <fstream>
std::vector<long long> search_in_file(const std::string& path, const std::string& pattern) {
    std::vector<long long> positions;
    if (pattern.empty()) return positions;
    const std::size_t chunk_size = 1 << 20;
    const std::size_t keep = pattern.size() - 1;
    std::ifstream f(path, std::ios::binary);
    std::vector<char> chunk(chunk_size);
    std::string buf;            // 이전 꼬리 + 새 청크
    long long buf_start = 0;    // buf[0]의 파일 내 오프셋
    while (f.read(chunk.data(), static_cast<std::streamsize>(chunk.size())) || f.gcount() > 0) {
        buf.append(chunk.data(), static_cast<std::size_t>(f.gcount()));
        for (int p : kmp_search(buf, pattern)) positions.push_back(buf_start + p);
        if (buf.size() > keep) {
            std::size_t drop = buf.size() - keep;
            buf.erase(0, drop);
            buf_start += static_cast<long long>(drop);
        }
    }
    return positions;
}

테스트 검증

#include <cassert>
void test_string_algorithms() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    auto kmp_pos = kmp_search(text, pattern);
    auto rk_pos = rabin_karp_search(text, pattern);
    auto bm_pos = boyer_moore_search(text, pattern);
    auto z_pos = z_search(text, pattern);
    assert(kmp_pos.size() == 1 && kmp_pos[0] == 10);
    assert(rk_pos == kmp_pos);
    assert(bm_pos == kmp_pos);
    assert(z_pos == kmp_pos);
    // 빈 패턴
    assert(kmp_search("hello", "").empty());
    // 패턴이 텍스트보다 긴 경우
    assert(kmp_search("ab", "abc").empty());
}

LPS·Bad Character 캐싱 (반복 검색)

동일 패턴으로 여러 텍스트를 검색할 때, LPS 또는 Bad Character 테이블을 한 번만 구축해 재사용합니다.

// 패턴이 고정된 경우: LPS를 한 번만 구축해 재사용
// kmp_search(text, pattern) 대신 lps를 인자로 받는 오버로드를 두면
// 동일 패턴으로 여러 텍스트 검색 시 build_lps 호출을 생략할 수 있음
class CachedKmpSearcher {
public:
    explicit CachedKmpSearcher(std::string pattern)
        : pattern_(std::move(pattern)), lps_(build_lps(pattern_)) {}
    std::vector<int> search(const std::string& text) const;
private:
    std::string pattern_;
    std::vector<int> lps_;
};

비동기 대용량 검색 (참고)

파일이 매우 클 때는 std::async로 청크별 검색을 병렬화할 수 있습니다. 청크 경계에 패턴이 걸치지 않도록 오버랩(패턴 길이 - 1)을 두고 읽습니다.

---

참고 자료

• cppreference - string
• cppreference - algorithm
• LeetCode - String
• 《Introduction to Algorithms》(CLRS) - 32장 문자열 매칭

---

같이 보면 좋은 글

• STL 알고리즘 기본기: sort·find·count·transform·accumulate·copy·remove와 Ranges
• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
• C++ 분할정복
• C++ 자료구조 구현 실습: 해시테이블, 트라이 자동완성, O(1) LRU 캐시, Skip List 성능 비교

---