Algorithm Guidecomplexity: O(n + m)

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

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

KMP · pattern "ABABC"

text

pattern

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

Logic Node1 / 7

Live Python

1def build_lps(pattern):

2 lps = [0] * len(pattern)

3 length, i = 0, 1

4 while i < len(pattern):

5 if pattern[i] == pattern[length]:

6 length += 1

7 lps[i] = length

8 i += 1

9 elif length:

10 length = lps[length - 1]

11 else:

12 lps[i] = 0

13 i += 1

14 return lps

16def kmp(text, pattern):

# lps = [0,0,1,2,0]

17 lps = build_lps(pattern)

18 i = j = 0

19 while i < len(text):

20 if text[i] == pattern[j]:

21 i += 1; j += 1

22 if j == len(pattern):

23 return i - j

24 elif j:

25 j = lps[j - 1]

26 else:

27 i += 1

28 return -1

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

Guide Progress0%