Oh My Algorithm
Algorithm Guidecomplexity: O(n + m)

KMP 문자열 탐색 (Knuth-Morris-Pratt)

실패 함수(LPS)를 미리 계산해, 불일치가 나도 패턴을 처음부터 다시 비교하지 않고 건너뛰는 문자열 탐색입니다. 텍스트 포인터를 되돌리지 않아 O(n+m)에 매칭합니다.

01KMP 문자열 탐색 (Knuth-Morris-Pratt)

KMP 시작. 실패 함수 LPS로 'ABABC'의 접두사 정보를 미리 계산해, 불일치가 나도 텍스트를 되돌리지 않고 패턴만 건너뜁니다.

패턴을 텍스트 맨 앞에 맞춰 봅니다. 앞 네 글자 ABAB까지는 그대로 일치합니다.

다섯 번째 글자에서 갈립니다. 텍스트는 D, 패턴은 C입니다.

일치했던 ABAB의 끝 AB는 패턴의 앞부분과 같습니다. 그만큼만 패턴을 두 칸 당기지만, 여기서도 어긋납니다.

재활용할 접두사가 더 없어 패턴을 다섯 칸 뒤로 옮깁니다. 텍스트를 읽던 자리는 되돌리지 않는 것이 KMP의 핵심입니다.

옮긴 자리에서 ABABC 다섯 글자가 모두 일치합니다.

탐색 완료 · 패턴은 인덱스 5에서 시작합니다. 텍스트를 한 번도 되돌리지 않아 O(n+m)에 끝납니다.

text
A
B
A
B
D
A
B
A
B
C
A
B
A
B
A
B
C
pattern
1 / 7

02 쉽게 이해하기

For Everyone
🔑핵심 동작

실패했을 때 이미 맞춘 부분에서 다시 시작할 자리를 미리 표로 만들어 둡니다. 그래서 본문을 되돌아가지 않고 한 번만 훑습니다.

💡쉽게 말하면

패턴의 실패 함수(LPS)를 미리 계산해, 불일치가 나도 텍스트를 되돌리지 않고 패턴만 건너뜁니다.

비교를 낭비하지 않아 O(n+m)에 매칭해요.

📍어디에 쓰나
  • –텍스트 검색
  • –로그·DNA 서열 매칭
  • –grep류 도구

03 파이썬 구현 코드

KMP 문자열 탐색 (Knuth-Morris-Pratt)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py
def build_lps(pattern):
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp(text, pattern):
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
            if j == len(pattern):
                return i - j
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return -1

04 자주 묻는 질문

FAQ
KMP 문자열 탐색 (Knuth-Morris-Pratt)란 무엇인가요?+

실패 함수(LPS)를 미리 계산해, 불일치가 나도 패턴을 처음부터 다시 비교하지 않고 건너뛰는 문자열 탐색입니다. 텍스트 포인터를 되돌리지 않아 O(n+m)에 매칭합니다.

KMP 문자열 탐색 (Knuth-Morris-Pratt)의 시간복잡도는 어떻게 되나요?+

KMP 문자열 탐색 (Knuth-Morris-Pratt)의 시간복잡도는 O(n + m) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

KMP 문자열 탐색 (Knuth-Morris-Pratt)은(는) 어디에 사용하나요?+

텍스트 검색, 로그·DNA 서열 매칭, grep류 도구.

KMP 문자열 탐색 (Knuth-Morris-Pratt)를 쉽게 비유하면?+

실패했을 때 이미 맞춘 부분에서 다시 시작할 자리를 미리 표로 만들어 둡니다. 그래서 본문을 되돌아가지 않고 한 번만 훑습니다.

→ 문자열 전체 보기Related
🔤라빈-카프 (Rabin-Karp)
평균 O(n + m)
🔤보이어-무어 (Boyer-Moore)
최선 O(n / m)