APS.04 String Matching

1. 문자열 패턴 매칭 문제란?

텍스트 $T = t_1 t_2 \cdots t_n$ (길이 $n$) 안에서 패턴 $P = p_1 p_2 \cdots p_m$ (길이 $m \le n$) 이 등장하는 모든 위치를 찾는 문제다.

$$T[s+1 \cdots s+m] = P[1 \cdots m] \quad (0 \le s \le n-m)$$

$s$ 는 shift — 패턴을 텍스트 위에 갖다 댈 시작 위치다. $s \le n-m$ 인 이유는 그 이상이면 패턴이 텍스트 밖으로 삐져나오기 때문이다.

2. Naive way

가장 단순한 접근: 모든 $s$ 에 대해 패턴을 처음부터 비교한다.

def string_matching_naive(T: str, P: str):
    n = len(T)
    m = len(P)
    shifts = []
    for s in range(n - m + 1):
        for j in range(m):
            if T[s + j] != P[j]:
                break
        else:
            shifts.append(s)
    return shifts

시간복잡도: $O\big((n-m+1) \cdot m\big) = O(nm)$

최악의 경우 — T = "aaa...a", P = "aa...ab" 처럼 매번 마지막 글자에서만 불일치가 나면 항상 $m$ 번을 다 써야 한다.

3. KMP (Knuth-Morris-Pratt) 알고리즘

핵심 관찰

나이브는 불일치 시 맞춰둔 $j$ 개의 정보를 전부 버리고 $s+1$ 로 이동한다.

그런데 우리는 이미 $T[s+1 \cdots s+j] = P[1 \cdots j]$ 라는 사실을 알고 있다. 텍스트 포인터 $i$ 는 절대 뒤로 가지 않는다. 불일치 시 패턴 포인터 $j$ 만 $\pi[j-1]$ 로 줄인다.

Prefix Function (접두사 함수)

$\pi[i]$ = $P[0 \cdots i]$ 에서 자기 자신을 제외한 접두사이면서 동시에 접미사인 것 중 가장 긴 길이.

자기 자신을 제외하는 이유: 포함하면 $i = \pi[i]$ 가 되어 무한루프. 항상 $\pi[i] < i$ 가 성립해야 한다.

def compute_prefix_function(P: str):
    m = len(P)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and P[j] != P[i]:
            j = pi[j - 1]
        if P[j] == P[i]:
            j += 1
        pi[i] = j
    return pi

시간복잡도: $O(m)$

※ 왜 불일치 시 $j = \pi[j-1]$ 인가?

P[i] ≠ P[j] 일 때, $j$ 를 무작정 0으로 되돌리면 틀린다. 예시로 확인해보자.

패턴 abcaaxabcab 에서 $i=10$, $j=3$ 까지 채워진 상황:

$$\pi = [0,\ 0,\ 0,\ 1,\ 1,\ 0,\ 1,\ 2,\ 3,\ 4,\ ?]$$

$P[i] = \texttt{b}$, $P[j] = \texttt{a}$ 로 불일치. LPS 길이 5는 불가.

왜 $j=0$ 으로 가면 안 되나?

$i-1$ 번째까지의 부분 문자열 abcaaxabca 의 LPS 길이는 $\pi[i-1] = 4$ — 접두사 abca 와 접미사 abca 가 같다. 이 4글자짜리 접두사/접미사 자체는 LPS 길이가 1이다 (a). 즉:

$$\text{`abcaaxabca’의 접두사 == 접미사 길이} = 4, \quad \text{그 다음으로 긴 길이} = 1$$

$j=0$ 으로 가버리면 이미 알고 있는 “길이 1짜리 일치” 정보를 버리게 된다.

올바른 이동: $j = \pi[j-1]$

$j-1$ 번째까지 접두사 안에서의 “접두사 = 접미사” 길이가 $\pi[j-1]$ 에 저장되어 있다. 이 위치로 $j$ 를 옮기면 이미 매칭된 부분을 재활용할 수 있다.

$$j = \pi[j-1] = \pi[2] = 0 \xrightarrow{\text{다시 비교}} P[i]=P[j] \implies \pi[i] = j+1 = 1$$

$j$ 를 한 번에 0으로 보내는 게 아니라, while 루프로 $\pi$ 를 타고 내려가며 일치하는 지점을 찾거나 $j=0$ 에 도달한다. 이 과정이 분할상환 $O(m)$ 을 보장한다.

KMP 매칭

def string_matching_kmp(T: str, P: str):
    n, m = len(T), len(P)
    pi = compute_prefix_function(P)
    shifts = []
    q = 0
    for i in range(n):
        while q > 0 and P[q] != T[i]:
            q = pi[q - 1]      # 폴백 — i는 고정, q만 줄임
        if P[q] == T[i]:
            q += 1
        if q == m:
            shifts.append(i - m + 1)
            q = pi[q - 1]
    return shifts

시간복잡도: $O(n+m)$

4. Rabin-Karp 알고리즘

글자를 하나씩 비교하는 대신, 부분 문자열 전체를 숫자(해시)로 바꿔서 비교한다.

$$\text{hash}(P) = \left(p_1 d^{m-1} + p_2 d^{m-2} + \cdots + p_m d^0\right) \bmod q$$

Rolling Hash

$$t_{s+1} = \left(d \cdot (t_s - T[s+1] \cdot h) + T[s+m+1]\right) \bmod q, \quad h = d^{m-1} \bmod q$$

앞 글자 빼고 → 왼쪽으로 shift → 새 글자 더하기. 이전 해시에서 $O(1)$ 에 다음 해시 계산.

def string_matching_rabin_karp(T: str, P: str, d=256, q=10**9+7):
    n, m = len(T), len(P)
    h = pow(d, m - 1, q)
    p, t = 0, 0
    for i in range(m):
        p = (d * p + ord(P[i])) % q
        t = (d * t + ord(T[i])) % q
    shifts = []
    for s in range(n - m + 1):
        if p == t and T[s:s + m] == P:
            shifts.append(s)
        if s < n - m:
            t = (d * (t - ord(T[s]) * h) + ord(T[s + m])) % q
    return shifts

시간복잡도: $O(n+m)$ expected

4.1 해시 충돌 확률과 기대 spurious hit 수

해시 함수가 $\bmod, q$ 에서 균등 분포한다고 가정하면, 서로 다른 두 문자열 $X \neq Y$ 에 대해

$$\Pr[,\text{hash}(X) = \text{hash}(Y),] = \frac{1}{q}$$

즉 spurious hit(해시는 같지만 실제 문자열은 다른 경우)이 발생할 확률은 각 윈도우마다 $\frac{1}{q}$.

텍스트에 총 $n - m + 1$ 개의 윈도우가 있으므로, 기대 spurious hit 수는

$$\mathbb{E}[,\text{spurious hits},] = \frac{n - m + 1}{q}$$

$q$ 를 충분히 큰 소수(예: $10^9 + 7$)로 잡으면 이 값은 사실상 0에 가깝다. spurious hit이 발생해도 문자열 전체를 $O(m)$ 으로 검증하면 되므로, 전체 기대 시간복잡도는 $O(n + m)$ 이 된다.

Spurious Hit

해시가 같아도 실제 문자열이 다를 수 있다 — Spurious Hit.

• Strict Verification: 해시 일치 시 실제 문자열 직접 비교
• Double Hashing: 독립적인 해시 두 개 사용. 충돌 확률 $\frac{1}{q_1 \cdot q_2} \approx 0$

기댓값 분석: $q = 10^9+7$ 이면 $n = 10^9$ 텍스트에서도 Spurious Hit 기댓값 $\approx 1$ 회.

5. Problem 4.2 — String Exponentiation

문자열 $S$ 가 주어질 때, $S = A^k$ 를 만족하는 최대 $k$ 를 구하라.

핵심 관찰

$S = A^k$ 이면 $S$ 는 주기 $p = |A|$ 를 가진다. 즉 $S[i] = S[i+p]$ 가 모든 유효한 $i$ 에 대해 성립.

$\pi[n-1]$ 은 $S$ 전체에서 접두사 = 접미사인 가장 긴 길이이므로, 겹치는 부분의 길이가 $\pi[n-1]$ 이고 겹치지 않는 최소 반복 단위의 길이가

$$p = n - \pi[n-1]$$

판별 규칙

$$k = \begin{cases} n/p & n \bmod p = 0 \ 1 & \text{otherwise} \end{cases}$$

$n \bmod p = 0$ 이 아니면 $S$ 는 완전한 반복이 아니므로 $k = 1$.

예시: $S = \texttt{abcabcabc}$

$$n = 9,\quad \pi[n-1] = 6,\quad p = 9 - 6 = 3,\quad 9 \bmod 3 = 0 \implies k = \frac{9}{3} = 3$$

접두사 abcabcabc 와 접미사 abcabcabc 가 길이 6 만큼 겹친다 — 즉 반복 단위 abc 가 3번 등장.

알고리즘

1. $\pi$ 배열 계산
2. $p = n - \pi[n-1]$
3. $n \bmod p = 0$ 이면 $k = n/p$, 아니면 $k = 1$

def maximum_exponent(s: str):
    n = len(s)
    pi = compute_prefix_function(s)
    period = n - pi[-1]
    if n % period == 0:
        return n // period
    else:
        return 1

6. Problem 4.3 — Longest Repeated Substring

6.1 문제 정의

• 입력: 소문자 영문자로 구성된 길이 $n$ 의 문자열 $S$
• 출력: $S$ 에서 두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이 $L$
• 조건: 두 등장 위치가 겹쳐도 됨 (overlapping 허용)

$S = \texttt{banana}$ 에서 두 번 이상 나오는 부분 문자열 중 가장 긴 것은?

• b → 1번만 → ✗
• an → $S[1..2]$, $S[3..4]$ → ✓
• ana → $S[1..3]$, $S[3..5]$ → ✓ (겹쳐도 됨!)
• anan → 1번만 → ✗

→ 답: $L = 3$

6.2 접근법 1 — DP: $O(n^2)$

아이디어: 모든 접미사 쌍 $(S[i:],\ S[j:])$ 의 LCP(Longest Common Prefix)를 DP 테이블로 구한다.

$$dp[i][j] = \text{LCP}(S[i:],\ S[j:]) = \begin{cases} dp[i+1][j+1] + 1 & S[i] = S[j] \ 0 & \text{otherwise} \end{cases}$$

답 $= \max_{i \neq j} dp[i][j]$

한계: 테이블 크기 $O(n^2)$, 시간·공간 모두 $O(n^2)$.

6.3 접근법 2 — KMP: $O(n^2)$

아이디어: 각 접미사 $S[i:]$ 에 대해 prefix function을 계산한다. $\pi[k]$ 의 최댓값이 그 접미사 내에서 가장 긴 “접두사 = 접미사” 길이이므로 반복 부분문자열 후보가 된다.

한계: 접미사가 $n$ 개, 각 prefix function 계산이 $O(n)$ → 전체 $O(n^2)$.

6.4 접근법 3 — Rabin-Karp + 이진탐색: $O(n \log n)$

핵심 관찰 — 단조성

check(L) = “길이 $L$ 인 중복 부분문자열이 존재하는가?”

길이 $L$ 짜리가 두 번 나오면, 그 앞 $L-1$ 글자도 반드시 두 번 나온다:

$$\text{check}(L) = \text{True} \implies \text{check}(L-1) = \text{True}$$

유효한 길이 집합은 항상 ${0, 1, \ldots, k}$ 형태 → 이진탐색으로 최대 $k$ 탐색 가능.

check(L) 구현 — Rolling Hash

고정된 $L$ 에 대해 길이 $L$ 창을 슬라이드하며 해시를 집합에 넣는다. 해시 충돌 시 실제 문자열로 검증.

S = b a n a n a,  L = 3

창[0]: "ban" → hash=H1 → seen={H1:[0]}
창[1]: "ana" → hash=H2 → seen={H1:[0], H2:[1]}
창[2]: "nan" → hash=H3 → seen={..., H3:[2]}
창[3]: "ana" → hash=H2 → H2 이미 있음! "ana"=="ana" → True ✓

rolling hash 갱신 $O(1)$:

$$h_{s+1} = \bigl(d \cdot h_s - S[s] \cdot d^L + S[s+L]\bigr) \bmod q$$

이진탐색 흐름

left=0, right=n, ans=0
while left <= right:
    mid = (left+right) // 2
    if check(mid):      # 길이 mid 중복 존재
        ans = mid
        left = mid + 1  # 더 길어도 가능?
    else:
        right = mid - 1 # 더 짧은 것만 가능
return ans

시간복잡도: check $O(n)$ × 이진탐색 $O(\log n)$ = $O(n \log n)$

def has_duplicate_substring(T: str, L: int, d=256, q=10**9+7) -> bool:
    n = len(T)
    if L == 0:
        return True
    if L > n:
        return False
    h = pow(d, L - 1, q)
    t = 0
    for i in range(L):
        t = (d * t + ord(T[i])) % q
    seen = {t: [0]}
    for s in range(1, n - L + 1):
        t = (d * (t - ord(T[s - 1]) * h) + ord(T[s + L - 1])) % q
        if t in seen:
            current = T[s:s + L]
            for prev in seen[t]:
                if T[prev:prev + L] == current:
                    return True
            seen[t].append(s)
        else:
            seen[t] = [s]
    return False


def longest_repeated(n: int, s: str) -> int:
    def bin_search(left: int, right: int) -> int:
        if left > right:
            return right
        mid = (left + right) // 2
        if has_duplicate_substring(s, mid):
            return bin_search(mid + 1, right)
        else:
            return bin_search(left, mid - 1)
    return bin_search(0, n)

7. 알고리즘 종합 비교

패턴 매칭 알고리즘

KMP vs Rabin-Karp: 둘 다 $O(n+m)$ 이지만 접근이 다르다.

• KMP는 결정론적 — 해시 충돌 없이 항상 정확.
• Rabin-Karp는 확률론적 — 여러 패턴 동시 검색에 유리.

응용 문제 알고리즘