Knuth-Morris-Pratt (KMP 알고리즘)

 

✅Knuth-Morris-Pratt (KMP 알고리즘)

 

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색(String Matching) 알고리즘 중 하나로, 텍스트에서 특정 패턴을 효율적으로 찾을 수 있는 방법입니다.

• 일반적인 브루트 포스(완전 탐색) 방법(O(NM))은 불필요한 비교가 많아 비효율적입니다.
• KMP는 접두사-접미사 배열(Prefix Table, LPS 배열) 을 활용하여 중복되는 비교를 줄여 O(N + M) 시간 복잡도로 최적화합니다.

---

1️⃣ KMP 알고리즘이 필요한 이유

문자열 검색을 수행할 때, 일반적인 브루트 포스 방식을 사용하면 최악의 경우 O(NM) 시간이 걸립니다.
하지만 KMP 알고리즘을 사용하면 O(N + M) 으로 줄일 수 있습니다.

✔ KMP의 핵심 아이디어

1. 패턴 내에서 발생하는 반복 구조를 활용하여 불필요한 비교를 줄임.
2. LPS(Longest Prefix Suffix) 배열을 사용하여 패턴의 이전 매칭 정보를 저장.
3. 일치하지 않는 경우에도 이동할 위치를 미리 결정하여 불필요한 연산을 줄임.

---

2️⃣ LPS(Longest Prefix Suffix) 배열 생성 (O(M))

KMP의 핵심은 LPS 배열을 미리 계산하는 것입니다.
LPS 배열은 어떤 부분 문자열에서 접두사(prefix)와 접미사(suffix)가 같은 최대 길이를 저장합니다.

🔹 LPS 배열 예시:
문자열 "ABABAC" 의 LPS 배열을 계산해 보겠습니다.

 

패턴	A	B	A	B	A	C
LPS	0	0	1	2	3	0

✔ LPS 배열의 의미

• LPS[i] 는 0부터 i까지의 부분 문자열에서 접두사와 접미사가 일치하는 최대 길이를 의미합니다.
• 예를 들어 "ABABAC"의 LPS[4] = 3 은 "ABA" 가 앞과 뒤에서 일치하는 최대 길이가 3임을 의미합니다.

✔ LPS 배열 생성 코드

def compute_lps(pattern):
    M = len(pattern)
    lps = [0] * M
    j = 0  # 접두사 길이

    for i in range(1, M):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]

        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j

    return lps

pattern = "ABABAC"
print(compute_lps(pattern))  # [0, 0, 1, 2, 3, 0]

📌 이 코드의 시간 복잡도는 O(M)입니다.

---

3️⃣ KMP 알고리즘을 사용한 문자열 검색 (O(N + M))

KMP는 LPS 배열을 활용하여 텍스트에서 패턴을 빠르게 검색합니다.

✔ KMP 알고리즘 구현

def kmp_search(text, pattern):
    N, M = len(text), len(pattern)
    lps = compute_lps(pattern)
    j = 0  # 패턴 포인터
    result = []

    for i in range(N):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]

        if text[i] == pattern[j]:
            j += 1
            if j == M:
                result.append(i - M + 1)
                j = lps[j - 1]  # 다음 탐색을 위해 LPS 활용

    return result

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern))  # [10]

📌 O(N + M)으로 빠르게 검색이 가능하며, 패턴이 여러 번 등장하는 경우에도 활용 가능.

---

4️⃣ KMP 알고리즘 정리

알고리즘 단계	설명	시간 복잡도
LPS 배열 생성	패턴 내 접두사-접미사 일치 정보 저장	O(M)
문자열 검색	LPS 배열을 활용하여 불필요한 비교 제거	O(N)
전체 시간 복잡도	O(N + M)

✔ KMP 알고리즘을 활용하면 문자열 검색을 빠르게 수행할 수 있음.
✔ 특히, 패턴이 반복되는 경우에도 O(N) 안에 탐색이 가능하여 효율적임.