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

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

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

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

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

Q: 더 깊이 공부하려면?

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

2026년 4월 7일 · 40분 읽기 · 수정 2026년 4월 7일 고급 실습

이 글의 핵심

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

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

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

100만 글자 분량의 로그 파일에서 특정 에러 패턴을 찾을 때, 단순 반복문으로 검색하면 수 초가 걸립니다. 비유하면 “한 글자씩 전부 비교하는 것”과 “KMP·라빈카프로 불필요한 비교를 건너뛰는 것”의 차이입니다. 아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 실행 예제
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. 문제 시나리오

시나리오 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)에 검색 가능합니다.

알고리즘 선택 가이드

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

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

2.1 문제 정의

패턴 매칭: 텍스트 T(길이 n)에서 패턴 P(길이 m)가 등장하는 모든 시작 위치를 찾는 문제. 아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

단순 검색 (브루트포스): 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ❌ 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)에 결정합니다. 한 번 비교한 문자를 다시 비교하지 않습니다. 아래 코드는 mermaid를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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”가 접두사이자 접미사 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 구현

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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 활용: 문자열 반복 주기

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 문자열이 어떤 패턴의 반복으로 이루어졌는지 판별
// "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)에 갱신합니다. 해시가 같으면 추가로 문자별 비교(충돌 처리). 아래 코드는 mermaid를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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 구현

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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글자) 해시 교집합으로 계산합니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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)에 가깝게 동작합니다. 아래 코드는 mermaid를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

5.2 Bad Character 테이블

아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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)에 구합니다. 다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 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 접미사 배열 구축 (단순 정렬)

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 접미사 배열 + 이진 탐색으로 패턴 검색

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 접미사 배열에서 패턴이 등장하는 범위 [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)에 구할 수 있습니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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] 수행. 아래 코드는 cpp를 사용한 구현 예제입니다. 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ❌ 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로 음수 방지. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌ 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 조건 확인. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌
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처럼 패턴과 텍스트에 없는 구분자를 삽입합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌ 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 범위 보장. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌
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)에 구축합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌ 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으로 충돌 확률을 더 낮출 수 있습니다. 다음은 간단한 cpp 코드 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ❌ 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 ≤ 100	n > 10만	KMP 또는 Boyer-Moore	O(n+m) 보장, Boyer-Moore가 평균 더 빠름
m > 100	대용량	Boyer-Moore	Bad Character로 큰 점프
다중 패턴 (동일 길이)	임의	Rabin-Karp	한 번 스캔으로 여러 패턴 검색
접두사/접미사 분석	임의	Z 알고리즘	O(n) 선형 시간
반복 검색, LCP	n 고정	접미사 배열	O(n log n) 구축 후 O(m log n) 검색

9.2 const 참조와 reserve 활용

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// ✅ 텍스트·패턴을 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 테스트 케이스 필수 항목

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 반드시 검증할 케이스
// 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 검색 엔진 래퍼

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 테스트 검증

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 기준 (대략):

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

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

동일 패턴으로 여러 텍스트를 검색할 때, LPS 또는 Bad Character 테이블을 한 번만 구축해 재사용합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 패턴이 고정된 경우: 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 활용
핵심 원칙:

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

자주 묻는 질문 (FAQ)

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

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

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

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

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다. 한 줄 요약: KMP·라빈카프·접미사 배열을 마스터할 수 있습니다.

참고 자료

cppreference - string
cppreference - algorithm
LeetCode - String
《Introduction to Algorithms》(CLRS) - 32장 문자열 매칭
《알고리즘 설계》 - Kleinberg, Tardos

이 글의 핵심

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

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

목차

1. 문제 시나리오

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

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

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

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

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

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

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

알고리즘 선택 가이드

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

2.1 문제 정의

3. KMP 알고리즘

3.1 핵심 아이디어

3.2 실패 함수 (LPS) 구축

3.3 완전한 KMP 구현

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

4. Rabin-Karp 알고리즘

4.1 핵심 아이디어

4.2 완전한 Rabin-Karp 구현

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

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

5. Boyer-Moore 알고리즘

5.1 핵심 아이디어

5.2 Bad Character 테이블

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

6. Z 알고리즘

6.1 핵심 아이디어

6.2 Z 배열 구축

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

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

7. 접미사 배열

7.1 핵심 아이디어

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

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

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

7.5 LCP 배열 구축 (선택)

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

에러 1: KMP LPS 인덱스 오류

에러 2: Rabin-Karp 해시 오버플로우

에러 3: Boyer-Moore Bad Character 인덱스

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

에러 5: 빈 패턴 처리 누락

에러 6: unsigned char 변환 누락

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

에러 8: Rabin-Karp base·mod 선택 오류

9. 베스트 프랙티스

9.1 알고리즘 선택 기준

9.2 const 참조와 reserve 활용

9.3 경계 조건 일관 처리

9.4 테스트 케이스 필수 항목

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

10. 성능 최적화 팁

10.1 알고리즘별 적용 상황

9.2 Rabin-Karp 모듈러 선택

10.3 Boyer-Moore 사전 필터

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

10.5 메모리 최적화

11. 프로덕션 패턴

11.1 검색 엔진 래퍼

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

10.3 테스트 검증

11.4 실무 활용 사례

11.5 성능 벤치마크 (참고)

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

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

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

12. 구현 체크리스트

정리

자주 묻는 질문 (FAQ)

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

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

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다. 한 줄 요약: KMP·라빈카프·접미사 배열을 마스터할 수 있습니다.

참고 자료

관련 글

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