단순 문자열 탐색·롤링 해시·충돌

겹치는 모든 일치를 찾고 Rabin–Karp의 해시 후보를 실제 문자로 확인합니다.

문서에서 특정 패턴의 모든 시작 위치를 찾고 싶습니다. 목표는 연속 일치의 명세와 해시 충돌 검사를 이해하는 것입니다. 문자열 인덱스·나머지 연산·입출력 약속을 복습하세요.

개념과 약속

입력은 text와 pattern, 출력은 모든 일치 시작 인덱스의 오름차순 목록입니다. 겹치는 일치도 포함합니다. 빈 패턴은 각 문자 사이와 양 끝의 n+1개 경계에 일치한다고 약속합니다. 패턴이 더 길면 일치는 없습니다.

단순 탐색은 가능한 시작점마다 해당 구간의 실제 문자열을 비교합니다. Rabin–Karp는 구간을 숫자로 압축한 해시를 먼저 비교합니다. 문자열의 문자 코드들을 밑 base의 다항식처럼 합쳐 modulus로 나눈 나머지를 저장합니다. 한 칸 이동할 때 맨 앞 항을 빼고 나머지를 한 자리 밀어 새 문자를 더하는 것이 롤링 해시입니다. 서로 다른 문자열도 같은 해시가 될 수 있으므로 해시가 같을 때 실제 문자열도 비교합니다.

손으로 상태 추적하기

text=ABABA, pattern=ABA입니다.

시작 i	구간	실제 일치
0	ABA	참
1	BAB	거짓
2	ABA	참

modulus=1이면 모든 해시가 0이지만 실제 비교 덕분에 i=1은 정답에 들어가지 않습니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def naive_matches(text, pattern):
    return [i for i in range(len(text) - len(pattern) + 1) if text[i:i + len(pattern)] == pattern]


def rabin_karp(text, pattern, base=256, modulus=101):
    if base < 1 or modulus < 1:
        raise ValueError("positive base and modulus required")
    n, m = len(text), len(pattern)
    if not m:
        return list(range(n + 1))
    if m > n:
        return []
    highest = pow(base, m - 1, modulus)
    pattern_hash = window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % modulus
        window_hash = (window_hash * base + ord(text[i])) % modulus
    matches = []
    for i in range(n - m + 1):
        if pattern_hash == window_hash and text[i:i + m] == pattern:
            matches.append(i)
        if i < n - m:
            window_hash = ((window_hash - ord(text[i]) * highest) * base + ord(text[i + m])) % modulus
    return matches


print(naive_matches("ABABA", "ABA"))
print(rabin_karp("ABABA", "ABA"))
print(rabin_karp("ABABA", "ABA", modulus=1))
print(rabin_karp("AB", ""))
print(rabin_karp("AB", "ABC"))