코딩 테스트 문자열 알고리즘

문자열 문제는 브루트포스로 두면 쉽게 $O(NM)$ 이 됩니다. 네 가지 패턴으로 선형 또는 준선형까지 줄이는 기준을 정리합니다.

문자열 문제는 무엇을 찾느냐에 따라 알고리즘이 갈립니다. 한 패턴의 위치, 접두사를 공유하는 사전, 반복되는 조각, 조건을 만족하는 연속 구간처럼 찾는 대상이 제각각입니다. 어느 쪽이든 이중 반복문으로 비교하면 입력이 조금만 커져도 시간 초과가 납니다. 그래서 문제 유형을 먼저 분류하고 거기에 맞는 알고리즘을 고르는 순서가 중요합니다.

문제 유형과 선택 기준

먼저 풀어야 할 질문을 한 줄로 정리하면 알고리즘이 거의 정해집니다. 아래 표는 자주 나오는 네 유형과 권장 알고리즘, 그 복잡도입니다. $N$ 은 본문 길이, $M$ 은 패턴 길이, $L$ 은 단어 하나의 길이입니다.

문제 유형	추천 알고리즘	복잡도
한 문자열에서 패턴 찾기	KMP	$O(N+M)$
부분 문자열 동일성 비교 반복	롤링 해시	평균 $O(1)$ 비교
다수 문자열의 접두사 탐색	트라이(Trie)	삽입·탐색 $O(L)$
연속 구간 조건 만족	슬라이딩 윈도우	$O(N)$

같은 분류를 흐름도로 보면 선택이 더 분명해집니다. 판별 기준은 본문에서 무엇을 찾는가 하나입니다.

표와 흐름도가 가리키는 핵심은 같습니다. 비교 한 번의 비용을 줄이거나, 비교 자체를 건너뛰거나, 같은 접두사를 한 번만 저장해 브루트포스가 버리는 정보를 살리는 것입니다.

브루트포스의 한계

부분 문자열 탐색을 가장 단순하게 짜면 본문의 모든 시작 위치마다 패턴을 끝까지 맞춰 봅니다. 시작 위치가 $N$ 개, 매번 최대 $M$ 글자를 비교하므로 최악에는 $O(NM)$ 입니다. aaaa...ab에서 aaaab를 찾는 경우처럼 거의 맞다가 마지막에 어긋나는 입력이 최악을 만듭니다.

문제는 어긋났을 때 본문 포인터를 한 칸 뒤로 되돌리고 패턴을 처음부터 다시 맞춘다는 점입니다. 이미 본문의 앞부분을 봤는데 그 정보를 버리는 셈입니다. KMP와 롤링 해시는 이 낭비를 서로 다른 방식으로 없앱니다.

KMP 패턴 매칭

KMP(Knuth-Morris-Pratt)는 패턴 안의 반복 구조를 미리 계산해 두고, 어긋났을 때 본문 포인터를 되돌리지 않는 알고리즘입니다. 핵심은 실패 함수라고도 부르는 pi 배열입니다. pi[i]는 패턴의 0번부터 i번까지 부분 문자열에서 접두사와 접미사가 일치하는 가장 긴 길이를 담습니다.

pi 배열이 있으면 패턴의 j번에서 어긋났을 때 j를 pi[j-1]로 점프시켜 비교를 이어갑니다. 이미 일치한 접두사만큼은 다시 볼 필요가 없기 때문입니다.

python

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

prefix_function("ababa")는 [0, 0, 1, 2, 3]을 돌려줍니다. 이 배열을 본문 탐색에 그대로 씁니다. 본문 포인터 i는 한 번도 뒤로 가지 않고, 패턴 포인터 j만 pi를 따라 점프합니다.

python

def kmp_search(text, pat):
    pi = prefix_function(pat)
    res = []
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pat[j]:
            j = pi[j - 1]
        if text[i] == pat[j]:
            j += 1
            if j == len(pat):
                res.append(i - j + 1)
                j = pi[j - 1]
    return res

kmp_search("ababababa", "aba")는 [0, 2, 4, 6]을 반환합니다. 본문과 패턴 포인터가 각각 한 방향으로만 움직이므로 전체가 $O(N+M)$ 입니다. pi 배열의 마지막 값은 패턴의 최소 반복 단위를 구할 때도 쓰여서, 문자열의 주기를 묻는 문제에 그대로 응용됩니다.

롤링 해시

롤링 해시는 부분 문자열을 정수 하나로 바꿔 비교를 $O(1)$ 에 가깝게 만드는 기법입니다. 이를 패턴 탐색에 쓴 것이 Rabin-Karp 알고리즘입니다. 문자열을 정해진 진법(base)의 수로 보고, 창을 한 칸 옮길 때 맨 앞 글자를 빼고 맨 뒤 글자를 더해 해시를 갱신합니다. 매번 전체를 다시 계산하지 않는 점이 핵심입니다.

값이 커지면 오버플로가 나므로 큰 소수로 나눈 나머지를 씁니다. 아래는 base를 131, 모듈러를 $2^{61}-1$ 로 둔 예시입니다. $2^{61}-1$ 은 메르센 소수라 나머지 연산에 흔히 쓰고, base 131도 충돌을 줄이려고 자주 고르는 소수입니다.

python

def rabin_karp(text, pat, base=131, mod=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m > n:
        return []
    high = pow(base, m - 1, mod)
    ph = th = 0
    for i in range(m):
        ph = (ph * base + ord(pat[i])) % mod
        th = (th * base + ord(text[i])) % mod
    res = []
    for i in range(n - m + 1):
        if ph == th and text[i:i + m] == pat:
            res.append(i)
        if i < n - m:
            th = ((th - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return res

rabin_karp("ababababa", "aba")도 [0, 2, 4, 6]을 돌려줍니다. 주의할 점은 해시가 같다고 문자열이 같지는 않다는 것입니다. 서로 다른 문자열이 같은 해시를 갖는 충돌이 생길 수 있어서, 위 코드는 ph == th일 때 실제 문자열을 한 번 더 비교합니다. 충돌 확률을 더 낮추려면 서로 다른 base·mod 쌍으로 해시를 두 번 계산하는 더블 해싱을 씁니다.

트라이

트라이(Trie)는 여러 문자열의 공통 접두사를 한 경로로 모으는 트리입니다. 단어 하나를 넣을 때 글자마다 자식 노드를 따라 내려가고, 단어가 끝나는 노드에 표시를 둡니다. 단어 길이가 $L$ 이면 삽입과 탐색이 모두 $O(L)$ 이라, 사전에 든 단어 수와 무관하게 한 단어 길이에만 비례합니다.

python

class TrieNode:
    def __init__(self):
        self.child = {}
        self.end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.child:
                cur.child[ch] = TrieNode()
            cur = cur.child[ch]
        cur.end = True
 
    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.child:
                return False
            cur = cur.child[ch]
        return True

starts_with는 접두사 경로가 끝까지 존재하는지만 봅니다. end 표시는 정확히 그 단어가 사전에 있는지 구분할 때 씁니다. 접두사 충돌을 판별하는 문제에서는 단어를 넣는 중에 이미 끝난 노드를 지나가는지, 또는 넣은 뒤에도 자식이 남는지를 확인합니다.

다만 알파벳이 다양하고 단어가 많으면 노드 수가 빠르게 늘어 메모리가 부담입니다. 그래서 단순 포함 여부만 묻는다면 해시셋이 더 가벼울 때가 많습니다.

슬라이딩 윈도우와 투 포인터

슬라이딩 윈도우는 연속 구간을 다룰 때 양 끝점만 옮겨 $O(N)$ 에 푸는 패턴입니다. 오른쪽 포인터로 창을 넓히고, 조건을 어기면 왼쪽 포인터로 창을 줄입니다. 문자열에서는 중복 없는 가장 긴 부분 문자열을 찾는 문제가 대표적입니다.

python

def longest_unique(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

longest_unique("abcabcbb")는 3, longest_unique("pwwkew")도 3을 반환합니다. 각 글자의 마지막 위치를 기억해 두고, 중복을 만나면 왼쪽 포인터를 그 위치 다음으로 당깁니다.

투 포인터는 비슷해 보이지만 적용 조건이 다릅니다. 아래 표로 구분을 정리합니다.

특성	투 포인터	슬라이딩 윈도우
정렬 필요	보통 필요	불필요
포인터 이동	양 끝에서 수렴 또는 같은 방향	오른쪽 확장·왼쪽 축소
적합한 문제	쌍 찾기, 구간 합	연속 부분 문자열

정리하면 투 포인터는 정렬된 데이터의 쌍을 찾을 때, 슬라이딩 윈도우는 연속 구간의 조건을 추적할 때 씁니다. 문자열 문제는 구간 조건이 많아 슬라이딩 윈도우 쪽이 자주 나옵니다.

자주 하는 실수

네 알고리즘 모두 구현에서 실수가 몰리는 지점이 있습니다. 아래는 시험장에서 자주 점수를 잃는 곳입니다.

KMP에서 어긋났을 때 while로 pi를 따라 점프하지 않고 j를 1씩 줄이면 $O(NM)$ 으로 퇴화합니다.
롤링 해시에서 모듈러를 빼먹어 오버플로가 나거나, 해시 충돌 검증을 생략해 오답이 납니다.
트라이 노드 수 폭증을 고려하지 않아 메모리 초과가 납니다.
대소문자·공백·유니코드 같은 전처리 규칙을 입력에서 놓칩니다.

마지막 항목은 알고리즘과 무관해 보여도 채점에서 자주 나오는 실패 원인입니다. 풀이를 짜기 전에 입력 문자 집합과 정규화 규칙을 먼저 적어 두는 습관이 안전합니다. 연습 문제로는 BOJ 1786(찾기)으로 KMP를, BOJ 5052(전화번호 목록)로 트라이 접두사 충돌을 직접 확인해 볼 수 있습니다.

정리

문자열 문제는 본문에서 무엇을 찾는가를 한 줄로 정의하면 알고리즘이 거의 정해집니다. 한 패턴의 출현은 KMP로 $O(N+M)$ , 같은 길이 조각의 반복 비교는 롤링 해시로 평균 $O(1)$ 비교에 처리합니다. 다수 단어의 접두사 질의는 트라이로 $O(L)$ , 연속 구간 조건은 슬라이딩 윈도우로 $O(N)$ 에 풉니다.

네 가지 모두 브루트포스가 버리는 정보를 재활용해 비교 비용을 줄인다는 공통점이 있습니다. 구현에서는 KMP의 점프, 롤링 해시의 충돌 검증, 트라이의 메모리, 입력 전처리 네 가지를 확인하면 흔한 감점을 피할 수 있습니다.