부분 문자열 매칭

부분 문자열 매칭은 긴 글 안에서 짧은 글이 어디에 나오는지 찾는 문제입니다. 넣는 것은 뒤질 대상인 긴 글과 찾을 짧은 글 두 개입니다. 답은 짧은 글이 나타나는 시작 위치들입니다. 편집기의 찾기 기능과 로그 검색이 이 문제를 풉니다.

상세

이 절은 부분 문자열 매칭이 무엇을 묻는 문제인지 먼저 세웁니다. 그다음 가장 쉬운 풀이가 언제 느려지는지 보고, 그 느림을 피하는 풀이들을 짧게 짚습니다.

예는 긴 글 ABABCABAB 와 짧은 글 ABAB 한 쌍을 주로 씁니다. 풀이마다 다른 예가 더 잘 보일 때만 따로 듭니다.

부분 문자열

문자열은 글자를 순서대로 늘어놓은 것입니다. 부분 문자열은 그 안에서 붙어 있는 구간 하나를 잘라 낸 조각입니다. ABABCABAB 에서 BCA 는 붙어 있는 세 글자라서 부분 문자열입니다.

글자를 건너뛰고 골라낸 조각은 부분 문자열이 아닙니다. ABABCABAB 에서 첫 A, 가운데 C, 끝 B 를 골라낸 ACB 는 사이가 벌어져 있습니다. 사이가 벌어져도 되는 조각은 부분 수열이라고 따로 부릅니다.

문제를 세우기

입력은 둘입니다. 뒤질 대상인 긴 문자열을 텍스트라고 부릅니다. 찾을 짧은 문자열은 패턴이라고 부릅니다. 텍스트 길이는 n, 패턴 길이는 m 으로 적습니다.

답은 패턴이 텍스트에 나타나는 시작 위치들입니다. 위치는 텍스트 맨 앞 글자를 0 으로 셉니다. 텍스트 ABABCABAB 에서 패턴 ABAB 는 0 과 5 에서 시작합니다.

나타난 곳끼리 겹쳐도 따로 셉니다. 텍스트 AAAA 에서 패턴 AA 는 0, 1, 2 세 곳에서 나타납니다. 쓰임에 따라 첫 위치 하나만 묻기도 하고, 나타나는지 아닌지만 묻기도 합니다.

하나씩 맞대 보는 풀이

가장 쉬운 풀이는 패턴을 텍스트 위에 맞대 놓고 한 칸씩 밀며 견주는 것입니다. 해 볼 수 있는 경우를 하나도 빼지 않고 해 본다는 뜻에서 브루트 포스 풀이라고 부릅니다.

시작 위치마다 패턴 첫 글자부터 텍스트 글자와 차례로 견줍니다. 끝까지 같으면 그 위치를 답에 넣습니다. 중간에 어긋나면 그 위치를 버립니다. 그리고 한 칸 옆으로 옮깁니다.

아래 표는 예제에서 시작 위치마다 몇 글자를 견줬는지 적은 것입니다.

시작 위치는 0 부터 5 까지 여섯 개입니다. 텍스트 길이 9 에서 패턴 길이 4 를 빼고 하나를 더한 수입니다. 찾은 두 곳을 빼면 대부분 첫 글자에서 어긋나 금방 다음 위치로 넘어갑니다.

같은 절차를 파이썬으로 옮기면 반복문 두 겹이 됩니다. 바깥 반복이 시작 위치를 옮깁니다. 안쪽 반복은 글자를 하나씩 견줍니다.

def find_all(text, pat):
    n, m = len(text), len(pat)
    out = []
    for i in range(n - m + 1):
        k = 0
        while k < m and text[i + k] == pat[k]:
            k += 1
        if k == m:
            out.append(i)
    return out

안쪽 반복은 글자가 어긋나는 순간 멈춥니다. 멈췄을 때 k 가 패턴 길이와 같으면 끝까지 맞은 것입니다.

함수를 앞의 예들에 돌려 보면 표와 같은 답이 나옵니다.

find_all("ABABCABAB", "ABAB")  # [0, 5]
find_all("AAAA", "AA")         # [0, 1, 2]
find_all("ABC", "D")           # []

느려지는 입력

이 풀이는 어긋나는 글자가 뒤에 있을수록 느려집니다. 최악의 경우는 위치마다 패턴 끝 글자에서야 어긋나는 입력입니다.

텍스트가 AAAAAAAA 처럼 A 만 이어지고 패턴이 AAAB 라고 해 봅니다. 어느 위치에 맞대도 앞의 A 세 개는 맞고 마지막 B 에서 어긋납니다. 그래서 위치마다 패턴 길이만큼 글자를 견줍니다.

크기를 키워 봅니다. 텍스트가 A 1만 개이고 패턴이 A 99 개 뒤에 B 하나라면 시작 위치는 9901 개입니다. 위치마다 100 글자를 견주니 99만 번 넘게 견줍니다. 텍스트를 한 번 훑는 데 드는 1만 번과 크게 차이 납니다.

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지 적는 약속입니다. 하나씩 맞대 보는 풀이는 최악에 O(nm) 입니다. 텍스트 길이와 패턴 길이를 곱한 모양으로 늘어난다는 뜻입니다.

보통의 글에서는 이만큼 늘어나지 않습니다. 대부분의 위치가 첫 글자 몇 개 안에서 어긋나기 때문입니다. 그래도 같은 글자가 길게 이어지는 데이터나 일부러 만든 입력을 받으면 최악이 드러납니다.

버리는 정보

이 풀이가 느린 까닭은 이미 본 글자를 잊기 때문입니다. 위치 0 에서 AAA 까지 맞았다면 텍스트 앞 세 글자가 A 라는 것을 이미 압니다. 그런데 위치 1 로 넘어가면 그 글자들을 처음부터 다시 견줍니다.

빠른 풀이들은 이 낭비를 서로 다른 방법으로 줄입니다. 이미 맞춘 글자를 기억해 텍스트를 되짚지 않는 풀이가 있습니다. 어긋난 글자를 보고 여러 칸을 건너뛰는 풀이도 있습니다. 글자 대신 숫자 하나로 조각을 견주는 풀이도 있습니다. 아래 세 소절이 이 셋을 하나씩 짚습니다.

맞춘 글자를 기억하는 풀이

Knuth-Morris-Pratt 알고리즘은 줄여서 KMP(Knuth-Morris-Pratt, 크누스-모리스-프랫) 알고리즘이라고 부릅니다. 만든 세 사람의 이름을 땄습니다. 이 풀이는 텍스트를 앞으로만 읽고 한 번도 뒤로 돌아가지 않습니다.

비결은 패턴 안의 반복을 미리 알아 두는 것입니다. 이 소절은 텍스트 ABABABC 에서 패턴 ABABC 를 찾다가 텍스트 위치 4 에서 어긋난 순간을 가지고 봅니다. 그 순간을 말하려면 낱말 둘이 필요합니다.

문자열의 앞에서부터 잘라 낸 조각을 접두사라고 합니다. 끝에서부터 잘라 낸 조각은 접미사라고 합니다. ABAB 의 접두사 AB 와 접미사 AB 는 같은 조각입니다.

KMP 는 어긋나기 직전까지 맞은 패턴 조각을 봅니다. 예에서는 ABAB 까지 맞았습니다. 이 조각 안에서 앞 두 글자 AB 와 끝 두 글자 AB 가 같습니다. 이렇게 접두사이면서 접미사이기도 한 것 가운데 가장 긴 것의 길이가 KMP 가 쓰는 값입니다(조각 자신은 빼고 셉니다).

아래 표의 각 행은 그 예에서 패턴을 어디에 맞댔는지 보여 줍니다.

첫 시도는 텍스트 위치 4 에서 어긋납니다. 그때까지 맞은 ABAB 는 끝의 AB 가 앞의 AB 와 같습니다. 패턴을 두 칸 밀면 패턴 앞 두 글자는 견주지 않아도 이미 맞습니다. 텍스트 위치 4 부터 이어서 견주면 됩니다. 이렇게 해서 위치 2 에서 시작하는 패턴을 찾습니다.

앞에서 본 길이가 곧 다시 견줄 곳입니다. ABAB 에서 그 길이는 2 이므로 패턴 위치 2 의 글자부터 다시 견줍니다. 이 길이는 텍스트와 상관없이 패턴만 보고 정해집니다.

패턴을 먼저 한 번 훑어 패턴의 앞부분마다 이 길이를 표로 만들어 둡니다. 「여기서 어긋나면 패턴의 어디부터 다시 견준다」를 적은 표입니다. 이 표를 실패 함수라고 부릅니다.

표를 만드는 데 O(m), 텍스트를 훑는 데 O(n) 이 듭니다. 합치면 최악에도 O(n+m) 입니다. 같은 글자가 길게 이어지는 입력에서도 텍스트 글자 하나를 여러 번 되짚지 않습니다.

어긋난 글자를 보고 건너뛰는 풀이

보이어-무어 알고리즘은 패턴을 끝 글자부터 거꾸로 견줍니다. 어긋나면 그 텍스트 글자가 패턴 안에 있는지 봅니다. 패턴에 아예 없는 글자라면 패턴이 그 글자에 걸쳐 놓일 수 없습니다. 그러니 패턴 길이만큼 한 번에 밉니다. 패턴 안에 있는 글자면 그 글자가 패턴에서 놓인 곳에 맞춰 밉니다.

이 규칙을 나쁜 문자 규칙이라고 부릅니다. 글자마다 몇 칸 밀지는 텍스트와 상관없이 패턴만 보고 정해집니다. 이것을 미리 표로 만들어 둔 것이 건너뛰기 표입니다.

텍스트 ABCDEFXYZ 에서 패턴 XYZ 를 찾아 봅니다. 처음에 패턴 끝 Z 를 텍스트 C 와 견줍니다. C 는 패턴에 없으니 세 칸 밉니다. 다음에는 F 와 견주고 또 세 칸 밉니다.

마지막에는 Z, Y, X 가 차례로 맞아 위치 6 에서 찾습니다. 텍스트 글자 9 개 가운데 5 개만 봤습니다. 하나씩 맞대 보는 풀이라면 9 개를 모두 봤을 것입니다.

패턴이 길수록 한 번에 더 멀리 건너뜁니다. 보통의 글에서는 텍스트 글자를 다 보지 않고 끝나는 일이 흔합니다.

나쁜 문자 규칙 하나만 쓰면 최악은 O(nm) 입니다. 텍스트가 A 만 이어지고 패턴이 BAAA 라고 해 봅니다. 끝에서부터 A 셋이 맞다가 맨 앞 B 에서 어긋납니다. 어긋난 텍스트 글자 A 를 패턴의 A 에 맞추면 오히려 뒤로 가므로 한 칸만 밉니다. 다른 규칙을 함께 써서 최악을 줄인 변형도 있습니다.

숫자 하나로 조각을 견주는 풀이

라빈-카프 알고리즘은 글자를 하나씩 견주는 대신 해시 함수를 씁니다. 해시 함수는 문자열을 받아 숫자 하나로 바꾸는 함수입니다. 같은 문자열은 언제나 같은 숫자가 됩니다.

먼저 패턴의 해시값을 구합니다. 그다음 텍스트 위에 패턴 길이만큼의 창을 놓고 한 칸씩 밀며 창의 해시값과 견줍니다. 숫자가 다르면 글자도 다르니 바로 다음 칸으로 넘어갑니다.

창을 한 칸 밀 때마다 해시를 처음부터 다시 구하면 느립니다. 그래서 빠지는 글자 몫을 빼고 들어오는 글자 몫을 더해 새 값을 구합니다. 이렇게 이전 값에서 이어 구하는 해시를 롤링 해시라고 합니다.

다른 문자열이 같은 숫자가 되는 일도 있습니다. 이것을 해시 충돌이라고 합니다. 그래서 숫자가 같으면 글자를 하나씩 견줘 확인합니다.

충돌이 드물면 패턴 해시를 구하는 시간까지 합쳐 평균 O(n+m) 에 끝납니다. 충돌이 잦으면 확인하는 일이 쌓여 최악 O(nm) 까지 늘어납니다.

이 풀이의 쓸모는 구현이 짧다는 것입니다. 길이가 같은 패턴 몇 개의 해시값을 함께 들고 창 하나와 견주는 쪽으로도 쉽게 넓힐 수 있습니다. 패턴이 많고 길이도 제각각이면 다음 소절의 아호-코라식 알고리즘이 맞습니다.

패턴이 여럿이거나 텍스트가 고정일 때

패턴이 수백 개라면 하나씩 따로 찾는 일도 수백 번이 됩니다. 아호-코라식 알고리즘은 패턴 전부를 한데 묶어 텍스트를 한 번만 훑습니다. 금칙어 목록으로 글을 걸러 내는 일에 씁니다.

묶는 데는 트라이를 씁니다. 트라이는 문자열들을 앞 글자부터 갈라지는 나무 모양으로 담는 자료구조입니다. HE 와 HIS 를 담으면 H 아래에서 E 와 I 로 가지가 갈립니다. 앞 글자가 같은 패턴들은 같은 길을 나눠 씁니다.

텍스트 글자를 하나 읽을 때마다 트라이에서 한 칸 내려갑니다. 길이 막히면 지금까지 읽은 글자의 끝부분과 같은 다른 가지로 옮겨 갑니다. 이 연결은 KMP 의 실패 함수처럼 미리 이어 둡니다. 패턴 끝에 닿으면 그 패턴을 찾은 것으로 적습니다.

텍스트는 한 번만 읽고 되짚지 않습니다. 대신 찾은 곳마다 적는 일이 따로 듭니다. 찾는 시간이 텍스트 길이와 찾은 개수를 더한 만큼 드는 까닭입니다.

반대로 텍스트가 고정인 경우도 있습니다. 텍스트는 두고 패턴만 바꿔 가며 여러 번 찾습니다. 큰 문서 묶음이나 유전자 서열에서 여러 번 찾을 때가 그렇습니다. 이때는 텍스트 쪽을 미리 손질해 둡니다.

접미사 배열이 그런 손질입니다. 텍스트의 모든 접미사를 사전 순으로 정렬해 둔 배열입니다. 어떤 부분 문자열이든 어느 접미사의 앞부분입니다. ABABCABAB 의 BCA 는 접미사 BCABAB 의 앞부분입니다.

그러니 정렬된 접미사들 가운데 패턴으로 시작하는 것을 이진 탐색으로 찾으면 됩니다. 이진 탐색은 정렬된 목록의 가운데를 보고 절반씩 버려 가며 찾는 방법입니다. 찾는 시간은 주로 패턴 길이에 따라 늘어납니다. 텍스트 길이에는 거의 매이지 않습니다.

접미사 트리는 같은 접미사들을 트라이처럼 나무로 엮어 둔 것입니다. 패턴 글자를 따라 나무를 내려가면 찾습니다. 두 구조 모두 텍스트 크기의 몇 배 되는 메모리를 씁니다.

풀이마다 드는 시간

지금까지 본 풀이를 한 표에 모읍니다. n 은 텍스트 길이, m 은 패턴 길이입니다. 찾는 데 드는 시간 칸은 미리 하는 일을 뺀 값입니다.

KMP 알고리즘부터 아호-코라식 알고리즘까지 넷은 패턴을 손질합니다. 맨 아래 하나는 텍스트를 손질합니다. 어느 쪽을 미리 손질할지가 풀이를 고르는 첫 갈림입니다.

풀이를 고르는 순서

아래 그림은 위에서부터 물어 처음 「예」가 나오는 풀이를 고르는 순서입니다.

flowchart TD
    A["찾을 패턴이 여럿인가"] -->|예| B["아호-코라식 알고리즘"]
    A -->|아니오| C["같은 텍스트에서 여러 번 찾나"]
    C -->|예| D["접미사 배열 · 접미사 트리"]
    C -->|아니오| E["최악 시간을 보장해야 하나"]
    E -->|예| F["KMP 알고리즘"]
    E -->|아니오| G["보이어-무어 알고리즘"]

텍스트가 짧으면 어느 풀이든 차이가 거의 없습니다. 그럴 때는 하나씩 맞대 보는 풀이로 충분합니다. 라빈-카프 알고리즘은 그림에 없습니다. 짧게 구현해야 하거나 길이가 같은 패턴 몇 개를 함께 찾을 때 고릅니다.

백엔드 코드에서 만나는 모습

백엔드 코드에서 이 문제는 대개 언어의 문자열 함수 뒤에 숨어 있습니다. 파이썬의 in 과 find, 자바의 contains 와 indexOf 가 부분 문자열 매칭을 합니다. 함수 안에서 어떤 풀이를 쓰는지는 언어와 판마다 다릅니다.

"ABABCABAB".find("ABAB")  # 0
"ABAB" in "ABABCABAB"     # True
"ABC".find("D")           # -1

find 는 첫 위치 하나만 돌려줍니다. 못 찾으면 -1 을 돌려줍니다. in 은 나타나는지 아닌지만 답합니다.

로그 파일을 grep 으로 뒤지는 일도 같은 문제입니다. 패턴에 글자 대신 규칙을 쓰면 정규 표현식 검색이 됩니다. 정규 표현식은 「숫자 세 개 뒤에 하이픈」처럼 글자의 모양을 패턴으로 적는 방법입니다.

데이터베이스의 LIKE 검색

데이터베이스에서는 LIKE '%timeout%' 같은 조건이 이 일을 합니다. SQL(Structured Query Language, 구조화 질의 언어)에서 % 는 아무 글자나 몇 개든 온다는 뜻입니다. 그래서 이 조건은 값 어딘가에 timeout 이 들어 있는 행을 찾습니다.

B-tree 인덱스는 값을 앞 글자부터 정렬해 둡니다. 앞이 정해진 LIKE 'time%' 은 인덱스로 범위를 좁힐 수 있습니다. 사전에서 「time」으로 시작하는 낱말을 찾아 펼치는 것과 같습니다.

앞이 % 로 열린 조건은 패턴이 값의 어디서 시작할지 모릅니다. 인덱스로 범위를 좁히지 못합니다. 행마다 부분 문자열 매칭을 하며 테이블을 처음부터 끝까지 읽게 됩니다. 이런 조건이 잦으면 낱말이나 글자 조각을 미리 색인해 두는 전문 검색으로 넘어갑니다.

같은 글자로 볼지 정하기

매칭은 글자가 같은지를 묻습니다. 그래서 무엇을 같은 글자로 볼지가 답을 바꿉니다. Error 를 찾을 때 error 도 찾아야 하면 양쪽을 소문자로 바꾼 뒤 견줍니다.

유니코드에서는 눈에 같은 글자가 다른 글자 묶음으로 적히기도 합니다. é 는 글자 하나로도, e 와 꾸밈표 둘로도 적을 수 있습니다. 둘을 같게 보려면 견주기 전에 유니코드 정규화로 한 가지 꼴로 맞춥니다.

관련 항목

부분 문자열 매칭이 속하는 상위 분류

알고리즘 · 문자열 알고리즘 · 탐색 알고리즘 · 계산 문제

부분 문자열 매칭 문제를 이루는 기본 개념

문자열 · 부분 문자열 · 접두사 · 접미사 · 빅오 표기법

부분 문자열 매칭을 푸는 알고리즘

브루트 포스 · Knuth-Morris-Pratt 알고리즘 · 보이어-무어 알고리즘 · 보이어-무어-호스풀 알고리즘 · 라빈-카프 알고리즘 · Z 알고리즘 · 아호-코라식 알고리즘

풀이가 기대는 자료구조와 기법

실패 함수 · 나쁜 문자 규칙 · 해시 함수 · 롤링 해시 · 해시 충돌 · 트라이 · 유한 오토마타

텍스트를 미리 색인해 두는 구조

접미사 배열 · 접미사 트리 · 이진 탐색 · 역색인 · 전문 검색 · B-tree · 인덱스

부분 문자열 매칭을 넓힌 문제

정규 표현식 · 근사 문자열 매칭 · 다중 패턴 매칭 · 편집 거리

이름이 닮아 헷갈리는 이웃 문제

부분 수열 · 최장 공통 부분 수열 · 최장 공통 부분 문자열 · 패턴 매칭

부분 문자열 매칭을 부르는 도구와 기능

grep · LIKE 연산자 · 파이썬 · 자바

견주기 전에 글자를 맞추는 처리

유니코드 · 유니코드 정규화 · 케이스 폴딩