26. KMP

KMP

빠른 설명

KMP(Knuth-Morris-Pratt)는 문자열에서 패턴을 빠르게 찾는 알고리즘이다. 실패했을 때 어디까지 되돌아가야 하는지를 prefix function으로 미리 계산한다.

언제 쓰는가

• 긴 문자열에서 특정 패턴이 등장하는 위치를 모두 찾을 때
• 단순 검색 $O(NM)$이 시간 초과가 날 때
• 접두사와 접미사 정보가 필요한 문자열 문제

시간복잡도

• 전처리: $O(M)$
• 검색: $O(N)$
• 전체: $O(N+M)$

참고자료

• CP-Algorithms - Prefix function / KMP
• Wikipedia - Knuth-Morris-Pratt algorithm
• GeeksforGeeks - KMP Algorithm
• 나무위키 - KMP 알고리즘

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
 
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
 
    return pi;
}
 
vector<int> kmp_search(const string& text, const string& pattern) {
    string combined = pattern + "#" + text;
    vector<int> pi = prefix_function(combined);
    vector<int> result;
    int m = pattern.size();
 
    for (int i = m + 1; i < (int)combined.size(); i++) {
        if (pi[i] == m) {
            result.push_back(i - 2 * m);
        }
    }
 
    return result;
}
 
int main() {
    auto pos = kmp_search("ababcababd", "abab");
    for (int x : pos) cout << x << ' ';
}

Python 코드

def prefix_function(s):
    pi = [0] * len(s)
 
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
 
    return pi
 
def kmp_search(text, pattern):
    combined = pattern + "#" + text
    pi = prefix_function(combined)
    result = []
    m = len(pattern)
 
    for i in range(m + 1, len(combined)):
        if pi[i] == m:
            result.append(i - 2 * m)
 
    return result
 
print(kmp_search("ababcababd", "abab"))