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

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

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

01 Explore How It Works

Interactive Step-by-Step
KMP · pattern "ABABC"
text
A
B
A
B
D
A
B
A
B
C
A
B
A
B
A
B
C
pattern

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

Logic Node1 / 7

02 Understand It Simply

For Everyone
🔑Analogy

헛걸음을 기억해두는 똑똑한 찾기 — 이미 맞춰본 부분은 다시 보지 않습니다.

💡In Plain Words

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

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

📍Where It's Used
  • –텍스트 검색
  • –로그·DNA 서열 매칭
  • –grep류 도구

03 Python Implementation

A clean, readable reference implementation of the core logic of 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 Frequently Asked Questions

FAQ
What is KMP 문자열 탐색 (Knuth-Morris-Pratt)?+

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

What is the time complexity of KMP 문자열 탐색 (Knuth-Morris-Pratt)?+

The time complexity of KMP 문자열 탐색 (Knuth-Morris-Pratt) is O(n + m). Follow the step-by-step visualization to see exactly why.

Where is KMP 문자열 탐색 (Knuth-Morris-Pratt) used?+

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

What's a simple analogy for KMP 문자열 탐색 (Knuth-Morris-Pratt)?+

헛걸음을 기억해두는 똑똑한 찾기 — 이미 맞춰본 부분은 다시 보지 않습니다.

→ Strings — see allRelated
🔤라빈-카프 (Rabin-Karp)
평균 O(n + m)
🔤보이어-무어 (Boyer-Moore)
최선 O(n / m)
Guide Progress0%