문자열 알고리즘: KMP와 롤링 해시 선택 전략

문자열 문제는 단순 비교로 시작하기 쉽지만, 길이가 커지면 곧 한계가 옵니다. 이때 KMP와 롤링 해시는 둘 다 유용하지만 쓰임이 다릅니다. KMP는 정확한 단일 패턴 탐색에 강하고, 롤링 해시는 빠른 후보 비교에 강합니다.

둘은 경쟁 관계가 아니라 선택/조합 대상입니다. 문제 조건(정확성 우선인지, 후보 비교가 많은지)을 우선 정하면 어떤 도구를 쓸지 명확해집니다. 여기서는 그 기준을 바로 적용할 수 있게 정리합니다.

핵심 패턴 청사진: KMP·롤링 해시

문자열 알고리즘은 정확 매칭이 필요한지, 후보를 빠르게 거를지를 우선 나누면 선택이 쉬워집니다. 문제를 보고 지금 필요한 쪽이 정확 매칭인지 후보 필터링인지 우선 표시하세요.

KMP는 불일치가 발생해도 이미 맞춘 접두/접미 정보를 재사용하는 정확 매칭 알고리즘입니다. pi 배열을 사용해 텍스트 포인터를 되돌리지 않고 O(N+M)에 검색을 수행합니다. 패턴 "ababd" 검색 중 불일치가 나면 pi 값으로 다음 비교 위치를 즉시 점프할 수 있습니다.

롤링 해시는 고정 길이 창을 이동하며 해시값을 빠르게 갱신하는 기법입니다. 부분문자열 해시를 O(1)에 업데이트해 대량 후보 비교를 빠르게 수행할 수 있습니다. 길이 5 창을 한 칸 옮길 때 앞 문자를 빼고 뒤 문자를 더해 해시를 즉시 갱신하는 방식이 기본입니다.

충돌 검증은 해시가 같을 때 실제 문자열 동일성을 추가로 확인하는 절차입니다. 해시 일치만으로는 참 동등성을 보장할 수 없어서 직접 비교나 이중 해시를 함께 사용합니다. 후보 위치 해시가 같으면 원문 문자열을 직접 비교해 오탐을 제거하면 안전성을 확보할 수 있습니다.

문자열 매칭 실전 장애와 연결하기

모든 문자열 문제를 KMP로 풀면 구현이 복잡해질 수 있고, 모든 문제를 해시로 풀면 충돌 검증 부담이 커집니다. 특히 다중 질의, 중복 부분문자열 탐색, 길이 기반 이진 탐색 문제는 해시가 훨씬 자연스러운 경우가 많습니다.

반대로 단일 패턴 정확 매칭은 KMP가 가장 예측 가능한 선택입니다.

패턴 매칭 테스트로 빠르게 재확인하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

텍스트에서 패턴을 찾는 두 접근을 비교해 봅니다.

텍스트: "ababcabcabababd"
패턴: "ababd"

KMP는 접두사 함수(pi)를 만들어 불일치 시 점프합니다.
롤링 해시는 길이 m 창을 이동하며 해시값을 갱신합니다.
해시가 같으면 최종 문자열 비교로 충돌을 확인합니다.
정확성 최우선이면 KMP, 대량 후보 비교면 해시가 유리합니다.

KMP/해시 적용 관찰 기준

아래 기준으로 1차 선택을 할 수 있습니다.

단일 패턴 정확 위치 찾기: KMP 우선
많은 구간을 빠르게 비교: 롤링 해시 우선
충돌 허용이 어려운 환경: KMP 또는 해시+문자검증
여러 패턴 동시 검색: Trie/Aho-Corasick까지 검토

문제 요구가 정확성 우선인지 속도 우선인지 우선 고정해야 합니다.

문자열 매칭: KMP 접두사 함수 + 검색

문제 의도: KMP 접두사 함수와 검색 루프를 결합해 정확 매칭을 구현합니다.
입력 예시: text="ababcabcabababd", pattern="ababd"
출력 예시: 매칭 시작 인덱스 [10]

main.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> buildPi(const string& pattern) {
    vector<int> pi(pattern.size(), 0);
    int j = 0;
    for (int i = 1; i < (int)pattern.size(); ++i) {
        while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
        if (pattern[i] == pattern[j]) pi[i] = ++j;
    }
    return pi;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    if (pattern.empty()) return {};
    vector<int> pi = buildPi(pattern);
    vector<int> matches;
    int j = 0;
    for (int i = 0; i < (int)text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
        if (text[i] == pattern[j]) {
            if (j == (int)pattern.size() - 1) {
                matches.push_back(i - (int)pattern.size() + 1);
                j = pi[j];
            } else {
                j++;
            }
        }
    }
    return matches;
}

int main() {
    string text = "ababcabcabababd";
    string pat = "ababd";
    auto out = kmpSearch(text, pat);
    for (int x : out) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static int[] buildPi(String pattern) {
        int[] pi = new int[pattern.length()];
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) j = pi[j - 1];
            if (pattern.charAt(i) == pattern.charAt(j)) pi[i] = ++j;
        }
        return pi;
    }

    static List<Integer> kmpSearch(String text, String pattern) {
        if (pattern.isEmpty()) return List.of();
        int[] pi = buildPi(pattern);
        List<Integer> matches = new ArrayList<>();
        int j = 0;
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = pi[j - 1];
            if (text.charAt(i) == pattern.charAt(j)) {
                if (j == pattern.length() - 1) {
                    matches.add(i - pattern.length() + 1);
                    j = pi[j];
                } else {
                    j++;
                }
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        System.out.println(kmpSearch("ababcabcabababd", "ababd"));
    }
}

main.py

def build_pi(pattern):
    pi = [0] * len(pattern)
    j = 0

    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j

    return pi

def kmp_search(text, pattern):
    if not pattern:
        return []

    pi = build_pi(pattern)
    j = 0
    matches = []

    i = 0
    while i < len(text):
        ch = text[i]
        while j > 0 and ch != pattern[j]:
            j = pi[j - 1]
        if ch == pattern[j]:
            if j == len(pattern) - 1:
                matches.append(i - len(pattern) + 1)
                j = pi[j]
            else:
                j += 1
        i += 1

    return matches

text = "ababcabcabababd"
pat = "ababd"
print(kmp_search(text, pat))
# 출력: [10]

main.rs

fn build_pi(pattern: &[u8]) -> Vec<usize> {
    let mut pi = vec![0usize; pattern.len()];
    let mut j = 0usize;
    for i in 1..pattern.len() {
        while j > 0 && pattern[i] != pattern[j] {
            j = pi[j - 1];
        }
        if pattern[i] == pattern[j] {
            j += 1;
            pi[i] = j;
        }
    }
    pi
}

fn kmp_search(text: &str, pattern: &str) -> Vec<usize> {
    if pattern.is_empty() {
        return vec![];
    }
    let t = text.as_bytes();
    let p = pattern.as_bytes();
    let pi = build_pi(p);
    let mut j = 0usize;
    let mut matches = Vec::new();

    for i in 0..t.len() {
        while j > 0 && t[i] != p[j] {
            j = pi[j - 1];
        }
        if t[i] == p[j] {
            if j == p.len() - 1 {
                matches.push(i + 1 - p.len());
                j = pi[j];
            } else {
                j += 1;
            }
        }
    }
    matches
}

fn main() {
    println!("{:?}", kmp_search("ababcabcabababd", "ababd"));
}

실패 함수 점프 선정 배경

pi[i]는 패턴 0..i 구간의 최대 border 길이입니다. 불일치 시 j를 뒤로 크게 이동하되 텍스트 포인터는 뒤로 가지 않아 선형 시간이 보장됩니다. 정확 매칭이 필수인 로그 검색, 토큰 탐색에서 안정적으로 사용됩니다.

평균 시간복잡도: O(N + M)
최악 시간복잡도: O(N + M)
공간복잡도: O(M)

문자열 매칭: 롤링 해시 기본 검색

문제 의도: 슬라이딩 해시로 후보 위치를 빠르게 찾고 최종 비교로 검증합니다.
입력 예시: 동일한 텍스트/패턴
출력 예시: 매칭 시작 인덱스 목록

main.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> rollingHashSearch(const string& text, const string& pattern, long long base = 911, long long mod = 1000000007) {
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0 || m > n) return {};

    long long power = 1;
    for (int i = 0; i < m - 1; ++i) power = (power * base) % mod;

    long long patHash = 0, winHash = 0;
    for (int i = 0; i < m; ++i) {
        patHash = (patHash * base + pattern[i]) % mod;
        winHash = (winHash * base + text[i]) % mod;
    }

    vector<int> ans;
    for (int i = 0; i <= n - m; ++i) {
        if (patHash == winHash && text.substr(i, m) == pattern) ans.push_back(i);
        if (i + m < n) {
            long long left = text[i];
            long long right = text[i + m];
            winHash = (winHash - left * power) % mod;
            if (winHash < 0) winHash += mod;
            winHash = (winHash * base + right) % mod;
        }
    }
    return ans;
}

int main() {
    auto ans = rollingHashSearch("ababcabcabababd", "ababd");
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> rollingHashSearch(String text, String pattern) {
        long base = 911L, mod = 1_000_000_007L;
        int n = text.length(), m = pattern.length();
        if (m == 0 || m > n) return List.of();

        long power = 1;
        for (int i = 0; i < m - 1; i++) power = (power * base) % mod;

        long patHash = 0, winHash = 0;
        for (int i = 0; i < m; i++) {
            patHash = (patHash * base + textChar(pattern, i)) % mod;
            winHash = (winHash * base + textChar(text, i)) % mod;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i <= n - m; i++) {
            if (patHash == winHash && text.substring(i, i + m).equals(pattern)) ans.add(i);
            if (i + m < n) {
                long left = textChar(text, i), right = textChar(text, i + m);
                winHash = (winHash - left * power) % mod;
                if (winHash < 0) winHash += mod;
                winHash = (winHash * base + right) % mod;
            }
        }
        return ans;
    }

    static int textChar(String s, int idx) {
        return (int) s.charAt(idx);
    }

    public static void main(String[] args) {
        System.out.println(rollingHashSearch("ababcabcabababd", "ababd"));
    }
}

main.py

def rolling_hash_search(text, pattern, base=911, mod=10**9 + 7):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    power = 1
    for _ in range(m - 1):
        power = (power * base) % mod

    pat_hash = 0
    win_hash = 0
    for i in range(m):
        pat_hash = (pat_hash * base + ord(pattern[i])) % mod
        win_hash = (win_hash * base + ord(text[i])) % mod

    ans = []
    for i in range(n - m + 1):
        if pat_hash == win_hash:
            # 충돌 방지를 위해 최종 문자 비교
            if text[i:i + m] == pattern:
                ans.append(i)

        if i + m < n:
            left = ord(text[i])
            right = ord(text[i + m])
            win_hash = (win_hash - left * power) % mod
            win_hash = (win_hash * base + right) % mod

    return ans

print(rolling_hash_search("ababcabcabababd", "ababd"))
# 출력: [10]

main.rs

fn rolling_hash_search(text: &str, pattern: &str, base: i64, modu: i64) -> Vec<usize> {
    let t = text.as_bytes();
    let p = pattern.as_bytes();
    let n = t.len();
    let m = p.len();
    if m == 0 || m > n {
        return vec![];
    }

    let mut power = 1_i64;
    for _ in 0..(m - 1) {
        power = (power * base) % modu;
    }

    let mut pat_hash = 0_i64;
    let mut win_hash = 0_i64;
    for i in 0..m {
        pat_hash = (pat_hash * base + p[i] as i64) % modu;
        win_hash = (win_hash * base + t[i] as i64) % modu;
    }

    let mut ans = Vec::new();
    for i in 0..=(n - m) {
        if pat_hash == win_hash && &text[i..i + m] == pattern {
            ans.push(i);
        }
        if i + m < n {
            let left = t[i] as i64;
            let right = t[i + m] as i64;
            win_hash = (win_hash - (left * power) % modu + modu) % modu;
            win_hash = (win_hash * base + right) % modu;
        }
    }
    ans
}

fn main() {
    println!("{:?}", rolling_hash_search("ababcabcabababd", "ababd", 911, 1_000_000_007));
}

해시 윈도우 갱신 선정 배경

윈도우를 한 칸 이동할 때 해시를 상수 시간으로 갱신합니다. 해시가 같아도 충돌 가능성이 있으므로 최종 문자열 비교를 추가해 정확성을 확보해야 합니다. 다중 패턴/다중 구간 비교로 확장하기 쉬운 것이 장점입니다.

평균 시간복잡도: O(N) + 검증비용
최악 시간복잡도: 충돌이 많으면 O(NM) 가능
공간복잡도: O(1) (전처리 최소형)

문자열 매칭: 이중 해시로 충돌 리스크 완화

문제 의도: 서로 다른 두 모듈러 해시를 결합해 충돌 확률을 낮춥니다.
입력 예시: 문자열 쌍 비교 ("abracadabra", "abracadabra")
출력 예시: true/false

main.cpp

#include <iostream>
#include <string>
using namespace std;

long long h(const string& s, long long base, long long mod) {
    long long x = 0;
    for (char ch : s) x = (x * base + ch) % mod;
    return x;
}

bool doubleHashEqual(const string& a, const string& b) {
    auto h1a = h(a, 911382323, 1000000007);
    auto h1b = h(b, 911382323, 1000000007);
    auto h2a = h(a, 972663749, 1000000009);
    auto h2b = h(b, 972663749, 1000000009);
    return h1a == h1b && h2a == h2b;
}

int main() {
    cout << doubleHashEqual("abracadabra", "abracadabra") << "\n";
    cout << doubleHashEqual("abc", "acb") << "\n";
    return 0;
}

Main.java

public class Main {
    static long h(String s, long base, long mod) {
        long x = 0;
        for (int i = 0; i < s.length(); i++) {
            x = (x * base + s.charAt(i)) % mod;
        }
        return x;
    }

    static boolean doubleHashEqual(String a, String b) {
        long h1a = h(a, 911382323L, 1_000_000_007L);
        long h1b = h(b, 911382323L, 1_000_000_007L);
        long h2a = h(a, 972663749L, 1_000_000_009L);
        long h2b = h(b, 972663749L, 1_000_000_009L);
        return h1a == h1b && h2a == h2b;
    }

    public static void main(String[] args) {
        System.out.println(doubleHashEqual("abracadabra", "abracadabra"));
        System.out.println(doubleHashEqual("abc", "acb"));
    }
}

main.py

def double_hash_equal(a, b):
    def h(s, base, mod):
        x = 0
        for ch in s:
            x = (x * base + ord(ch)) % mod
        return x

    h1a = h(a, 911382323, 10**9 + 7)
    h1b = h(b, 911382323, 10**9 + 7)
    h2a = h(a, 972663749, 10**9 + 9)
    h2b = h(b, 972663749, 10**9 + 9)

    return (h1a, h2a) == (h1b, h2b)

print(double_hash_equal("abracadabra", "abracadabra"))
print(double_hash_equal("abc", "acb"))
# 출력
# True
# False

main.rs

fn h(s: &str, base: i64, modu: i64) -> i64 {
    let mut x = 0_i64;
    for ch in s.bytes() {
        x = (x * base + ch as i64) % modu;
    }
    x
}

fn double_hash_equal(a: &str, b: &str) -> bool {
    let h1a = h(a, 911382323, 1_000_000_007);
    let h1b = h(b, 911382323, 1_000_000_007);
    let h2a = h(a, 972663749, 1_000_000_009);
    let h2b = h(b, 972663749, 1_000_000_009);
    (h1a, h2a) == (h1b, h2b)
}

fn main() {
    println!("{}", double_hash_equal("abracadabra", "abracadabra"));
    println!("{}", double_hash_equal("abc", "acb"));
}