C++ 문자열 알고리즘 완벽 가이드 | KMP·라빈카프·접미사 배열·Z 알고리즘 [실전]

· 40분 읽기 · 수정 고급 실습
C++ 문자열 알고리즘 완벽 가이드 | KMP·라빈카프·접미사 배열·Z 알고리즘 [실전]

이 글의 핵심

C++ 문자열 패턴 매칭: KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열. 문제 시나리오, 완전한 예제, 흔한 실수, 성능 팁, 프로덕션 패턴. 100만 글자 분량의 로그 파일에서 특정 에러 패턴을 찾을 때, 단순 반복문으로 검색하면 수 초가 걸립니다. 비유하면 "한 글자씩 전부 비교하는 것"과 "KMP·라빈카프로 불필요한 비교를 건너뛰는 것"의 차이입니다.

들어가며: “100만 글자에서 패턴 찾기가 10초나 걸려요”

문자열 알고리즘 선택의 함정

100만 글자 분량의 로그 파일에서 특정 에러 패턴을 찾을 때, 단순 반복문으로 검색하면 수 초가 걸립니다. 비유하면 “한 글자씩 전부 비교하는 것”과 “KMP·라빈카프로 불필요한 비교를 건너뛰는 것”의 차이입니다.

flowchart TD
  subgraph wrong["❌ 단순 검색 O(n×m)"]
    W1[텍스트 n, 패턴 m] --> W2[매 위치마다 m번 비교]
    W2 --> W3[100만 × 100 = 1억 번]
    W3 --> W4[수 초]
  end
  subgraph right["✅ KMP O(n+m)"]
    R1[실패 함수로 건너뛰기] --> R2[불필요한 비교 제거]
    R2 --> R3[100만 + 100 ≈ 100만 번]
    R3 --> R4[밀리초 단위]
  end

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, KMP·라빈카프·Boyer-Moore·Z 알고리즘·접미사 배열의 완전한 C++ 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

  • 문자열 패턴 매칭 알고리즘을 상황에 맞게 선택할 수 있습니다.
  • KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열을 직접 구현할 수 있습니다.
  • 흔한 실수를 피하고 성능을 최적화할 수 있습니다.

요구 환경: C++17 이상

목차

  1. 문제 시나리오
  2. 기본 개념: 패턴 매칭 개요
  3. KMP 알고리즘
  4. Rabin-Karp 알고리즘
  5. Boyer-Moore 알고리즘
  6. Z 알고리즘
  7. 접미사 배열
  8. 자주 발생하는 에러와 해결법
  9. 베스트 프랙티스
  10. 성능 최적화 팁
  11. 프로덕션 패턴
  12. 구현 체크리스트

1. 문제 시나리오

시나리오 1: 대용량 로그에서 에러 패턴 검색

상황: 100MB 로그 파일에서 "FATAL: connection timeout" 패턴이 등장하는 모든 위치를 찾아야 합니다.

잘못된 접근: std::string::find는 내부적으로 단순 검색을 사용할 수 있어, 패턴이 길고 텍스트가 클 때 O(n×m)에 가깝게 동작할 수 있습니다.

해결: KMP 또는 Boyer-Moore. KMP는 O(n+m) 보장, Boyer-Moore는 실무에서 평균적으로 더 빠릅니다.

시나리오 2: DNA 서열에서 유사 구간 탐색

상황: 두 DNA 서열(수만 bp)에서 동일한 부분 문자열을 찾아야 합니다.

잘못된 접근: 모든 부분 문자열을 나열해 비교하면 O(n² × m) 수준입니다.

해결: 접미사 배열 또는 해시(Rabin-Karp). 접미사 배열로 O(n log n) 구축 후 이진 탐색으로 O(m log n)에 검색 가능합니다.

시나리오 3: 표절 검사 - 문서 유사도

상황: 두 문서에서 “연속된 k글자”가 얼마나 겹치는지 계산해 유사도를 판단해야 합니다.

잘못된 접근: 모든 k-gram을 나열해 비교하면 메모리와 시간이 폭발합니다.

해결: Rabin-Karp 해시. 각 문서의 k-gram 해시를 O(n)에 계산하고, 해시 집합으로 교집합을 구합니다.

시나리오 4: 에디터 “찾기” 기능

상황: 수천 줄의 소스 코드에서 사용자가 입력한 검색어를 실시간으로 하이라이트해야 합니다.

잘못된 접근: 매번 전체 텍스트를 다시 스캔하면 타이핑할 때마다 지연이 발생합니다.

해결: Boyer-Moore (패턴이 길 때) 또는 KMP (빠른 구현). 짧은 패턴은 단순 검색도 충분합니다.

시나리오 5: 문자열 내 모든 회문 찾기

상황: 문자열에서 모든 회문(앞뒤가 같은 부분)의 개수 또는 최장 회문을 구해야 합니다.

잘못된 접근: 각 위치를 중심으로 확장하면 O(n²)인데, Manacher 알고리즘 없이는 짝수 길이 회문 처리가 까다롭습니다.

해결: Manacher 알고리즘 O(n) 또는 Z 알고리즘을 활용한 회문 판별.

시나리오 6: 네트워크 DPI·패킷 패턴 매칭

상황: 실시간 패킷 스트림에서 악성 시그니처(예: "GET /admin", 바이너리 시퀀스)가 포함된 패킷을 검출해야 합니다.

잘못된 접근: 패킷 전체를 메모리에 버퍼링한 뒤 단순 검색하면 지연과 메모리 부담이 큽니다.

해결: KMP 또는 Boyer-Moore로 스트리밍 검색. 청크 경계 오버랩을 두고 패턴이 걸쳐지지 않도록 처리합니다.

시나리오 7: 검색 엔진 자동완성·접두사 검색

상황: 수천 개의 키워드에서 사용자 입력과 일치하는 접두사를 가진 항목을 빠르게 찾아야 합니다.

잘못된 접근: 모든 키워드를 순회하며 strncmp하면 O(키워드 수 × 입력 길이)입니다.

해결: 접미사 배열 또는 트라이(Trie). 접미사 배열은 정렬된 접두사에서 이진 탐색으로 O(m log n)에 검색 가능합니다.

알고리즘 선택 가이드

문제 유형추천 알고리즘시간 복잡도
단일 패턴 매칭 (일반)KMPO(n + m)
단일 패턴 (실무 검색)Boyer-MooreO(n) 평균, O(n×m) 최악
다중 패턴, 해시 기반Rabin-KarpO(n + m) 평균
접두사-접미사 일치Z 알고리즘O(n)
부분 문자열 검색, LCP접미사 배열O(n log n) 구축, O(m log n) 검색

2. 기본 개념: 패턴 매칭 개요

2.1 문제 정의

패턴 매칭: 텍스트 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;
}

3. KMP 알고리즘

3.1 핵심 아이디어

KMP는 실패 함수(failure function)를 이용해, 불일치 시 이미 일치한 접두사를 활용해 되돌아갈 위치를 O(1)에 결정합니다. 한 번 비교한 문자를 다시 비교하지 않습니다.

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

3.2 실패 함수 (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;
}

3.3 완전한 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;
}

3.4 KMP 활용: 문자열 반복 주기

// 문자열이 어떤 패턴의 반복으로 이루어졌는지 판별
// "abcabcabc" -> 3 (abc 3번)
bool is_repeated(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> lps = build_lps(s);
    int period = n - lps[n - 1];
    return (n % period == 0 && period < n);
}

4. Rabin-Karp 알고리즘

4.1 핵심 아이디어

롤링 해시: 윈도우를 한 칸 옮길 때, 맨 앞 문자를 빼고 맨 뒤에 새 문자를 더하는 방식으로 해시를 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

4.2 완전한 Rabin-Karp 구현

#include <vector>
#include <string>
#include <cmath>

// Rabin-Karp: 롤링 해시 기반 패턴 매칭
// base=256, mod=큰 소수. 충돌 시 문자별 검증.
// 시간: 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 + pattern[i]) % mod;
    }

    // 첫 윈도우 해시
    int window_hash = 0;
    for (int i = 0; i < m; ++i) {
        window_hash = (static_cast<long long>(window_hash) * base + 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>(text[i]) * h % mod + mod) % mod;
            window_hash = (static_cast<long long>(window_hash) * base + text[i + m]) % mod;
        }
    }
    return positions;
}

4.3 표절 검사: 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 + doc[i]) % mod;
    hashes.insert(window);

    for (int i = k; i < n; ++i) {
        window = (window - static_cast<long long>(doc[i - k]) * h % mod + mod) % mod;
        window = (static_cast<long long>(window) * base + 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;
}

4.4 다중 패턴 검색 (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 + c) % mod;
        hash_to_patterns[h].push_back(p);
    }

    int n = static_cast<int>(text.size());
    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 + 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>(text[i]) * h % mod + mod) % mod;
            window_hash = (static_cast<long long>(window_hash) * base + text[i + m]) % mod;
        }
    }
    return results;
}

5. Boyer-Moore 알고리즘

5.1 핵심 아이디어

패턴을 오른쪽부터 왼쪽으로 비교합니다. 불일치 시 Bad Character와 Good Suffix 휴리스틱으로 여러 칸을 한 번에 건너뜁니다. 영어 등 자연어에서 평균 O(n/m)에 가깝게 동작합니다.

flowchart TD
  A[오른쪽부터 비교] --> B{불일치}
  B --> C[Bad Character: 불일치 문자가 패턴에 없으면 m칸 점프]
  B --> D[Good Suffix: 일치한 접미사가 패턴 앞쪽에 있으면 그 위치로]
  C --> E[최대 점프량 선택]
  D --> E
  E --> A

5.2 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;
}

5.3 완전한 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;
}

6. Z 알고리즘

6.1 핵심 아이디어

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

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

6.2 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;
}

6.3 Z 알고리즘으로 패턴 매칭

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

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

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

// s의 각 위치 i에서 s[0..]와 s[i..]의 최대 공통 접두사 길이
// 활용: 문자열 압축, 반복 패턴 탐지
std::vector<int> z_values = build_z(s);
// z_values[i] == i 이면 s[0..i-1]이 s[i..2i-1]과 완전 일치 (주기 i)
// 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;
}

7. 접미사 배열

7.1 핵심 아이디어

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

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

#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;
}

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

// 접미사 배열에서 패턴이 등장하는 범위 [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};
}

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

LCP 배열을 이용해 최장 반복 부분 문자열(Longest Repeated Substring)을 O(n)에 구할 수 있습니다.

// 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) : "";
}

7.5 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;
}

8. 자주 발생하는 에러와 해결법

에러 1: 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;
    }
}

에러 2: 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;

에러 3: 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;

에러 4: Z 알고리즘 구분자 누락

증상: pattern이 text의 접두사일 때, text 앞부분이 잘못 매칭으로 나옵니다.

원인: pattern + text만 이어붙이면, text가 pattern으로 시작할 때 Z값이 pattern 길이를 넘어설 수 있습니다.

해결: pattern + '$' + text처럼 패턴과 텍스트에 없는 구분자를 삽입합니다.

// ❌ text="aaa", pattern="aa" -> Z가 2,3,... 로 잘못 해석될 수 있음
std::string s = pattern + text;

// ✅
std::string s = pattern + '$' + text;

에러 5: 빈 패턴 처리 누락

증상: pattern이 빈 문자열일 때 무한 루프 또는 크래시.

원인: m == 0이면 lps가 비어 있고, 루프 조건이 잘못될 수 있습니다.

해결: 함수 시작 시 if (m == 0) return positions; 체크.

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

에러 6: unsigned char 변환 누락

증상: 한글 등 비ASCII 문자가 있을 때 bad_char[c] 인덱스가 256을 넘어 크래시.

원인: char가 signed면 128~255가 음수로 해석되어 큰 인덱스가 됩니다.

해결: static_cast<unsigned char>(c)로 0~255 범위 보장.

// ❌
bad_char[pattern[i]] = i;

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

에러 7: 접미사 배열 정렬 비교자 오류

증상: std::sort의 비교자에서 s.substr(a)를 사용하면 O(n) 비교 × O(n log n) 정렬로 O(n² log n)이 됩니다. 대용량에서 매우 느립니다.

원인: substr은 매번 새 문자열을 생성합니다.

해결: 인덱스만 전달하고 s.compare(a, n, s, b, n) 형태로 비교하거나, Doubling 기법으로 O(n log² n)에 구축합니다.

// ❌ O(n² log n) - substr이 매번 복사
std::sort(sa.begin(), sa.end(), [&s](int a, int b) {
    return s.substr(a) < s.substr(b);
});

// ✅ 인덱스 기반 비교 (또는 Doubling으로 rank 기반 정렬)
std::sort(sa.begin(), sa.end(), [&s, n](int a, int b) {
    return s.compare(a, n - a, s, b, n - b) < 0;
});

에러 8: 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;

9. 베스트 프랙티스

9.1 알고리즘 선택 기준

패턴 길이 m텍스트 길이 n권장 알고리즘이유
m < 8임의std::string::find 또는 단순 검색오버헤드가 알고리즘 이득보다 큼
8 ≤ m ≤ 100n > 10만KMP 또는 Boyer-MooreO(n+m) 보장, Boyer-Moore가 평균 더 빠름
m > 100대용량Boyer-MooreBad Character로 큰 점프
다중 패턴 (동일 길이)임의Rabin-Karp한 번 스캔으로 여러 패턴 검색
접두사/접미사 분석임의Z 알고리즘O(n) 선형 시간
반복 검색, LCPn 고정접미사 배열O(n log n) 구축 후 O(m log n) 검색

9.2 const 참조와 reserve 활용

// ✅ 텍스트·패턴을 const 참조로 전달해 불필요한 복사 방지
std::vector<int> kmp_search(const std::string& text, const std::string& pattern);

// ✅ 결과 벡터에 reserve로 재할당 최소화 (대략적 개수 예측 가능 시)
std::vector<int> positions;
positions.reserve(std::max(0, n - m + 1));  // 최대 매칭 개수

9.3 경계 조건 일관 처리

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

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

9.4 테스트 케이스 필수 항목

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

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

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

10. 성능 최적화 팁

10.1 알고리즘별 적용 상황

상황권장
패턴 짧음 (m < 10)단순 검색도 충분
패턴 길음, 텍스트 매우 김KMP 또는 Boyer-Moore
다중 패턴, 해시 활용Rabin-Karp
접두사/접미사 분석Z 알고리즘
부분 문자열 빈도, LCP접미사 배열

9.2 Rabin-Karp 모듈러 선택

// 64비트에서 오버플로우 없이 계산하려면
const uint64_t mod = (1ULL << 61) - 1;  // 메르센 소수
// 또는 double hashing으로 충돌 확률 감소

10.3 Boyer-Moore 사전 필터

실무에서는 해시로 1차 필터링 후, 일치 후보에서만 Boyer-Moore를 적용하는 하이브리드도 사용합니다.

9.4 접미사 배열 O(n) 구축

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

10.5 메모리 최적화

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

11. 프로덕션 패턴

11.1 검색 엔진 래퍼

#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);
    }
}

11.2 대용량 파일 스트리밍 검색

// 파일을 청크로 읽어가며 KMP 적용 (경계 처리 필요)
std::vector<long long> search_in_file(const std::string& path, const std::string& pattern) {
    std::vector<long long> positions;
    const size_t chunk_size = 1024 * 1024;  // 1MB
    std::vector<int> lps = build_lps(pattern);
    long long file_pos = 0;
    std::string overlap(pattern.size() - 1, '\0');  // 경계 오버랩

    std::ifstream f(path);
    std::string chunk;
    chunk.reserve(chunk_size + pattern.size());

    while (std::getline(f, chunk, '\0')) {  // 간략화: 실제로는 바이너리 읽기
        chunk = overlap + chunk;
        auto found = kmp_search(chunk, pattern);
        for (int p : found) {
            if (p >= static_cast<int>(overlap.size())) {
                positions.push_back(file_pos + p - overlap.size());
            }
        }
        overlap = chunk.substr(std::max(0, static_cast<int>(chunk.size()) - static_cast<int>(pattern.size()) + 1));
        file_pos += chunk.size() - overlap.size();
    }
    return positions;
}

10.3 테스트 검증

#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());
}

11.4 실무 활용 사례

도메인활용
로그 분석에러 패턴 검색, KMP/Boyer-Moore
DNA/생물정보서열 정렬, 접미사 배열, BLAST
표절 검사k-gram 해시, Rabin-Karp
에디터/IDE찾기/바꾸기, Boyer-Moore
네트워크패킷 패턴 매칭, DPI

11.5 성능 벤치마크 (참고)

n=1,000,000, m=100 기준 (대략):

알고리즘시간비고
단순 검색~100msO(n×m)
KMP~5msO(n+m)
Rabin-Karp~8ms해시 계산 오버헤드
Boyer-Moore~3ms평균적으로 가장 빠름
Z~6ms구분자 포함 문자열 2배

11.6 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_;
};

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

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

12. 구현 체크리스트

문자열 패턴 매칭을 구현할 때 다음을 확인하세요.

  • 빈 패턴 (m == 0) 처리했는가?
  • 패턴이 텍스트보다 긴 경우 (m > n) 조기 반환했는가?
  • KMP: j == 0일 때 lps[j-1] 접근하지 않았는가?
  • Rabin-Karp: long long과 (x + mod) % mod로 오버플로우·음수 방지했는가?
  • Boyer-Moore: s + m < n 범위 체크했는가?
  • Z 알고리즘: 구분자 $를 넣었는가?
  • 비ASCII 문자: unsigned char 캐스팅했는가?
  • 테스트: 경계 케이스(빈 문자열, 단일 문자, 반복 패턴)를 검증했는가?

정리

항목설명
KMP실패 함수로 O(n+m), 구현 단순
Rabin-Karp롤링 해시, 다중 패턴·표절 검사에 유리
Boyer-Moore오른쪽부터 비교, 실무 검색에 빠름
Z 알고리즘접두사-접미사, O(n)
접미사 배열부분 문자열 검색, LCP 활용

핵심 원칙:

  1. 패턴 길이와 텍스트 크기에 맞는 알고리즘을 선택한다.
  2. 경계 조건(빈 문자열, 인덱스)을 반드시 처리한다.
  3. 해시·인덱스 계산 시 오버플로우와 부호를 주의한다.
  4. 테스트 케이스로 검증한다.

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 텍스트 검색, DNA 서열 분석, 표절 검사, 로그 파싱, 에디터 검색 기능 등에 활용합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

한 줄 요약: KMP·라빈카프·접미사 배열을 마스터할 수 있습니다.

참고 자료

관련 글

  • C++ Algorithm Search |
  • C++ 알고리즘 |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3