연습 문제

이 장의 문제는 앞에서 배운 접두사 함수, 굴러가는 해시, 트라이를 그대로 응용하도록 만든 연습용 문제입니다. 먼저 순진한 풀이를 떠올리고, 어느 부분이 느린지 찾은 다음 알맞은 도구로 바꾸는 순서로 풀어 보세요. 아래 풀이에서 쓰는 prefix_function은 구현 장의 함수와 같습니다.

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

문제 1. 겹치는 모티프 세기

DNA 서열 seq(최대 100만 글자)와 모티프 motif가 주어집니다. 모티프가 서열에 몇 번 나타나는지 세세요. 출현끼리 겹쳐도 각각 셉니다. 예를 들어 seq = "AAAA", motif = "AA"이면 답은 3입니다.

접근: Python의 str.count는 겹치지 않는 출현만 세므로 답이 2가 됩니다. KMP로 훑으면서 발견 후 k = pi[m - 1]로 이어 가면 겹치는 출현까지 O(n + m)에 셀 수 있습니다.

def count_overlapping(seq: str, motif: str) -> int:
    pi = prefix_function(motif)
    m, k, count = len(motif), 0, 0
    for ch in seq:
        while k > 0 and ch != motif[k]:
            k = pi[k - 1]
        if ch == motif[k]:
            k += 1
        if k == m:
            count += 1
            k = pi[k - 1]
    return count


assert count_overlapping("AAAA", "AA") == 3
assert count_overlapping("ACGTACGTAC", "GTA") == 2

문제 2. 반복 단위 찾기

문자열 s가 어떤 문자열 u를 두 번 이상 이어 붙인 것인지 판별하고, 그렇다면 가장 짧은 u와 반복 횟수를 돌려주세요. 예를 들어 "xyzxyzxyz"는 ("xyz", 3)이고, "xyzxy"는 반복이 아니므로 None입니다.

접근: 길이 n인 문자열의 가장 긴 경계 길이가 b = pi[n - 1]이면 p = n - b는 문자열의 최소 주기입니다. n이 p로 나누어떨어지고 p < n이면 앞 p글자가 정확히 n / p번 반복된 것입니다.

def repeating_unit(s: str) -> tuple[str, int] | None:
    if not s:
        return None
    n = len(s)
    p = n - prefix_function(s)[-1]
    if p < n and n % p == 0:
        return s[:p], n // p
    return None


assert repeating_unit("xyzxyzxyz") == ("xyz", 3)
assert repeating_unit("xyzxy") is None
assert repeating_unit("aaaa") == ("a", 4)

문제 3. 두 번 나온 조각 찾기

로그 한 줄 s와 길이 L이 주어집니다. 길이 L인 부분 문자열 가운데 두 번 이상 나오는 것이 있으면, 두 번째 출현이 가장 먼저 끝나는 조각을 돌려주세요. 없으면 빈 문자열을 돌려줍니다.

접근: 모든 조각을 잘라 집합에 넣으면 O(n·L) 메모리가 듭니다. 굴러가는 해시로 창마다 해시값만 사전에 저장하고, 해시가 이미 있으면 실제 문자열을 비교해 확인합니다. 무작위 기수를 써서 의도적인 충돌을 막습니다.

import random


def first_repeat(s: str, L: int) -> str:
    if L <= 0 or L > len(s):
        return ""
    mod = (1 << 61) - 1
    base = random.randrange(256, mod - 1)
    high = pow(base, L - 1, mod)
    h = 0
    for ch in s[:L]:
        h = (h * base + ord(ch)) % mod
    seen: dict[int, list[int]] = {h: [0]}
    for i in range(1, len(s) - L + 1):
        h = ((h - ord(s[i - 1]) * high) * base + ord(s[i + L - 1])) % mod
        for j in seen.get(h, []):
            if s[j:j + L] == s[i:i + L]:
                return s[i:i + L]
        seen.setdefault(h, []).append(i)
    return ""


assert first_repeat("abcXabcY", 3) == "abc"
assert first_repeat("abcdef", 2) == ""

문제 4. 인기순 자동 완성

검색어와 검색 횟수 목록이 주어집니다. 접두사를 입력하면 그 접두사로 시작하는 검색어 가운데 횟수가 많은 순서로 최대 3개를 돌려주세요. 횟수가 같으면 사전순으로 앞선 것이 먼저입니다.

접근: 트라이의 단어 끝 노드에 횟수를 저장합니다. 접두사 노드까지 내려간 뒤 아래의 단어를 모두 모으고, (-횟수, 검색어) 기준으로 상위 3개를 고릅니다. 질의가 아주 많다면 노드마다 상위 3개를 미리 저장해 두는 방식으로 바꿀 수 있습니다.

import heapq


def build(queries: dict[str, int]) -> dict:
    root: dict = {}
    for q, cnt in queries.items():
        node = root
        for ch in q:
            node = node.setdefault(ch, {})
        node["$"] = cnt                     # "$"는 단어 끝 표시
    return root


def suggest(root: dict, prefix: str, k: int = 3) -> list[str]:
    node = root
    for ch in prefix:
        if ch not in node:
            return []
        node = node[ch]
    found, stack = [], [(node, prefix)]
    while stack:
        cur, word = stack.pop()
        for key, child in cur.items():
            if key == "$":
                found.append((-child, word))
            else:
                stack.append((child, word + key))
    return [w for _, w in heapq.nsmallest(k, found)]


root = build({"python": 50, "pytest": 30, "pyenv": 30, "pandas": 70, "pip": 10})
assert suggest(root, "py") == ["python", "pyenv", "pytest"]
assert suggest(root, "p") == ["pandas", "python", "pyenv"]
assert suggest(root, "z") == []

검색어에 $ 글자가 들어갈 수 있다면 단어 끝 표시를 별도 필드로 두어야 합니다.

정리

• 겹치는 출현은 발견 후 k = pi[m - 1]로 이어 가면 셀 수 있습니다.
• 최소 주기는 n - pi[n - 1]이며, 반복 문자열 판별에 바로 쓰입니다.
• 굴러가는 해시는 부분 문자열을 잘라 내지 않고 비교하게 해 주며, 해시가 같으면 반드시 확인합니다.
• 트라이 노드에 부가 정보(횟수 등)를 저장하면 자동 완성 순위를 매길 수 있습니다.