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

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

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

01 알고리즘 작동 원리 탐색

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 쉽게 이해하기

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)
Guide Progress0%