KMP 문자열 검색
KMP 알고리즘은 긴 텍스트에서 패턴이 나타나는 모든 위치를 찾는 문자열 검색 알고리즘입니다. 이름은 만든 사람인 크누스(Knuth), 모리스(Morris), 프랫(Pratt)의 첫 글자에서 왔습니다. 핵심은 이미 맞춰 본 글자를 다시 비교하지 않는 것이고, 그 덕분에 텍스트 길이 n, 패턴 길이 m에 대해 O(n + m) 시간에 검색합니다.
단순한 방법은 텍스트의 모든 위치에서 패턴을 처음부터 비교하다가 불일치가 나면 한 칸 밀고 처음부터 다시 비교합니다. 앞에서 맞춘 글자 정보를 버리기 때문에 최악에는 O(n × m)이 걸립니다. KMP는 패턴을 미리 분석해 "불일치가 났을 때 패턴을 어디까지 밀어도 안전한가"를 실패 함수라는 표로 만들어 두고, 텍스트 위치를 뒤로 되돌리지 않은 채 패턴만 이동합니다. 이 토픽에서는 실패 함수를 만드는 과정, 그것을 쓰는 검색 과정, 단순 검색과의 비교를 봅니다.
핵심 개념
문자열 검색
텍스트 안에서 패턴과 같은 부분 문자열의 시작 위치를 찾는 문제입니다. 모든 일치 위치를 구하거나 처음 하나만 구하기도 합니다.
핵심 개념
접두사와 접미사
문자열의 앞쪽 일부가 접두사, 뒤쪽 일부가 접미사입니다. ABAB의 접두사 AB와 접미사 AB는 같고, 이 겹침이 KMP가 재사용하는 정보입니다.
핵심 개념
실패 함수 π
π[i]는 패턴의 앞 i+1글자에서, 자기 자신을 제외하고 접두사이면서 접미사이기도 한 가장 긴 문자열의 길이입니다. 접두사 함수라고도 부릅니다.
핵심 개념
두 포인터 i와 j
i는 텍스트 위치, j는 지금까지 맞춘 패턴 글자 수입니다. 글자가 같으면 둘 다 전진하고, 다르면 j가 0보다 클 때 i는 두고 j만 π[j-1]로 줄이며 j가 0이면 i가 한 칸 전진합니다.
핵심 개념
텍스트를 되돌리지 않음
텍스트 위치 i는 한 번도 뒤로 가지 않습니다. 이미 맞춘 글자의 정보는 j에 담겨 있어서 같은 글자를 처음부터 다시 확인하지 않습니다.
핵심 개념
겹치는 일치
패턴을 모두 맞추면 j를 π[m-1]로 줄여 이어갑니다. 그러면 AAA 안의 AA처럼 서로 겹치는 일치도 놓치지 않고 찾습니다.
KMP의 배경
KMP 알고리즘은 1977년 크누스, 모리스, 프랫이 "Fast pattern matching in strings"라는 논문으로 함께 발표했고, SIAM Journal on Computing에 실렸습니다. 같은 해 보이어(Boyer)와 무어(Moore)도 평균적으로 아주 빠른 다른 검색 알고리즘을 발표했습니다. KMP의 실패 함수 아이디어는 1975년 아호-코라식(Aho-Corasick) 알고리즘이 여러 패턴을 한꺼번에 찾도록 확장하는 데 쓰였고, KMP는 그보다 앞선 1974년 기술 보고서로 먼저 알려졌습니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
KMP 알고리즘의 핵심 아이디어는?
불일치가 났을 때 이미 맞춘 글자의 정보를 실패 함수로 재사용해, 텍스트 위치를 되돌리지 않고 패턴만 이동하는 것입니다. 그래서 같은 글자를 처음부터 다시 비교하지 않습니다.
면접 질문
실패 함수(π 배열)는 무엇인가요?
π[i]는 패턴의 앞 i+1글자에서 접두사이면서 접미사인 가장 긴 (자기 자신을 제외한) 문자열의 길이입니다. 불일치 때 패턴을 얼마나 되돌려 이어 비교할 수 있는지를 알려 줍니다.
면접 질문
시간 복잡도가 O(n + m)인 이유는?
텍스트 위치 i는 앞으로만 가고, j는 한 칸씩 늘어나며 줄어드는 양이 늘어난 양을 넘을 수 없습니다. 그래서 검색의 총 이동이 O(n)이고, 같은 논리로 실패 함수 계산은 O(m)입니다.
면접 질문
문자열이 어떤 단위의 반복인지 알아내려면?
길이 n인 문자열의 마지막 π 값을 뺀 n − π[n-1]이 후보 단위의 길이이고, n이 그 값으로 나누어떨어지고 그 값이 n보다 작으면 그 단위가 반복된 문자열입니다.
활용 분야와 확장
함께 보면 좋은 토픽
참고 자료
Python — 실패 함수와 KMP 검색
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 def kmp_search(t, p): pi = prefix_function(p) found = [] j = 0 for i, c in enumerate(t): # i는 한 번도 뒤로 가지 않는다 while j > 0 and c != p[j]: j = pi[j - 1] # 패턴만 민다 if c == p[j]: j += 1 if j == len(p): found.append(i - j + 1) # 일치 시작 위치 j = pi[j - 1] # 겹치는 일치도 찾는다 return found print(prefix_function('ABABC')) # [0, 0, 1, 2, 0] print(kmp_search('ABABABCABABC', 'ABABC')) # [2, 7]
실패 함수 pi[i]는 패턴의 앞 i+1글자에서 자기 자신을 제외하고 접두사이면서 접미사이기도 한 가장 긴 문자열의 길이입니다. ABABC에서는 ABAB의 끝 AB가 앞 AB와 같아 pi[3] = 2이고, 나머지는 겹치는 부분이 없거나 1입니다. 패턴을 자기 자신 위에 겹쳐 밀며 구하므로 O(m)입니다. 검색에서는 텍스트 위치 i와 패턴 위치 j를 함께 움직입니다. 글자가 같으면 j를 늘리고, 다르면 i는 그대로 두고 j만 pi[j - 1]로 줄입니다. 이미 맞춘 ABAB 중 앞 AB는 다시 비교하지 않아도 되기 때문입니다. j가 패턴 길이에 닿으면 일치 하나를 찾은 것이고, 이어서 j를 pi[j - 1]로 줄여 겹치는 일치도 찾습니다. 위 텍스트에서는 위치 2와 7에서 일치합니다. 시각화의 실패 함수 만들기 탭과 KMP 검색 탭이 보여 주는 과정과 같습니다.
Python — 단순 검색과 비교 횟수
def naive_count(t, p): cmp = 0 for s in range(len(t) - len(p) + 1): for k in range(len(p)): cmp += 1 if t[s + k] != p[k]: break return cmp def kmp_count(t, p): pi = prefix_function(p) cmp = 0 j = 0 for c in t: while j > 0 and c != p[j]: cmp += 1 j = pi[j - 1] cmp += 1 if c == p[j]: j += 1 if j == len(p): j = pi[j - 1] return cmp print(naive_count('ABABABCABABC', 'ABABC'), kmp_count('ABABABCABABC', 'ABABC')) # 22 13 t = 'A' * 100 + 'B' p = 'A' * 20 + 'B' print(naive_count(t, p), kmp_count(t, p)) # 1701 181
단순 검색은 모든 시작 위치에서 패턴의 처음부터 비교하고, 불일치가 나면 한 칸 밀어 처음부터 다시 비교합니다. 위의 짧은 예에서는 글자 비교가 22번 대 13번으로 KMP가 적지만 차이가 크지 않습니다. 같은 글자가 길게 반복되는 입력에서는 차이가 커집니다. A가 100개 뒤에 B가 하나 있는 텍스트에서 A 20개와 B로 이루어진 패턴을 찾으면 단순 검색은 1701번, KMP는 181번 비교합니다. 단순 검색은 최악에 O(n × m)이고 KMP는 텍스트를 한 번만 훑어 O(n + m)이기 때문입니다.
Java — KMP 검색
static int[] prefixFunction(String p) { int[] pi = new int[p.length()]; int j = 0; for (int i = 1; i < p.length(); i++) { while (j > 0 && p.charAt(i) != p.charAt(j)) j = pi[j - 1]; if (p.charAt(i) == p.charAt(j)) j++; pi[i] = j; } return pi; } static List<Integer> search(String t, String p) { int[] pi = prefixFunction(p); List<Integer> res = new ArrayList<>(); int j = 0; for (int i = 0; i < t.length(); i++) { while (j > 0 && t.charAt(i) != p.charAt(j)) j = pi[j - 1]; if (t.charAt(i) == p.charAt(j)) j++; if (j == p.length()) { res.add(i - j + 1); j = pi[j - 1]; } } return res; } // prefixFunction("ABABC") → [0, 0, 1, 2, 0] // search("ABABABCABABC", "ABABC") → [2, 7]
자바 버전도 같은 구조입니다. 실패 함수를 한 번 만들어 두면 같은 패턴으로 여러 텍스트를 검색할 때 다시 계산하지 않아도 됩니다. 이 구현은 패턴이 빈 문자열이 아니라고 가정하므로, 실무에서는 빈 패턴을 먼저 걸러야 합니다. 자바 String.indexOf나 파이썬 str.find 같은 표준 함수로 단순한 검색은 해결됩니다. KMP는 알고리즘 교재의 표준 주제이고, 한 글자씩 들어오는 입력에서 j와 π 배열만으로 검색하거나 π 배열을 응용하는 문제에서 그 원리를 씁니다.
Q1
KMP 알고리즘의 핵심 아이디어는?
Q2
텍스트 길이 n, 패턴 길이 m일 때 KMP의 시간 복잡도는?
Q3
KMP의 실패 함수(pi 배열)에서 pi[i]가 뜻하는 것은?