C YC

IT Dev who working in Republic Of Korea

4 minute read

KMP알고리즘(Knuth Morris Pratt) 개념?

KMP(Knuth Morris Pratt) 알고리즘은 문자열 검색 알고리즘으로, 주어진 텍스트에서 특정 패턴이 존재하는 위치를 효율적으로 찾는 데 사용됩니다. 기본적인 브루트포스(Brute Force)방식과 달리, 불필요한 비교를 줄여 더 빠르게 동작하는게 특징입니다.

KMP 알고리즘은 두 가지 주요 과정으로 이루어집니다.

  1. 전처리 과정 (Partial Match Table 또는 LPS 배열 생성)
    • 패턴 내에서 자기 자신을 포함하는 가장 긴 접두사이자 접미사를 찾는 테이블을 만듭니다.
    • 이를 활용하면 불일치가 발생했을 때, 패턴을 처음부터 다시 검사할 필요 없이 적절한 위치에서 다시 비교를 시작할 수 있습니다.
  2. 검색 과정 (텍스트와 패턴 비교)
    • 전처리한 LPS(Longest Prefix Suffix) 배열을 이용하여 불필요한 비교 없이 빠르게 패턴을 찾습니다.

Image
(출처 : https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/)

LPS(Longest Prefix Suffix) 배열

LPS 배열은 패턴의 각 인덱스까지에서, 접두사(prefix)와 접미사(suffix)가 일치하는 최대 길이를 저장하는 배열로 KMP 알고리즘에서 불필요한 비교를 줄이기 위해 활용됩니다.

Image

  • "ABA"까지의 접두사와 접미사가 일치하는 최대 길이는 1 ("A")
  • "ABAB"의 접두사와 접미사가 일치하는 최대 길이는 2 ("AB")
  • "ABABA"의 접두사와 접미사가 일치하는 최대 길이는 3 ("ABA") 이 배열을 이용하면, 텍스트에서 불일치가 발생했을 때 패턴을 LPS 값을 참고해 점프할 수 있습니다.

LPS 배열의 개념

📌LPS 배열의 각 인덱스 i에 대해:

  • LPS[i] = X라면, 패턴의 처음 X개 문자(pattern[0:X-1])가 접두사이면서 접미사임을 의미합니다
  • 즉, 패턴의 일부를 일치시킨 후, 실패했을 때 어디로 이동해야 하는지를 나타냅니다.

❗ 접두사(Prefix)와 접미사(Suffix)의 개념

  • 접두사(Prefix): 문자열의 시작부터 일부까지 (“A”, “AB”, “ABA” 등)
  • 접미사(Suffix): 문자열의 끝에서 일부까지 (“A”, “BA”, “ABA” 등)
  • 접두사와 접미사는 전체 문자열과 같아서는 안됩니다.

LPS 배열 예제

Image

📌 LPS 배열 계산 과정

  1. “A”: 접두사, 접미사 없음 → LPS[0] = 0
  2. “AB”: 접두사 “A”, 접미사 “B” (일치하는 부분 없음) → LPS[1] = 0
  3. “ABA”: 접두사 “A”, “AB”, 접미사 “BA”, “A” → “A” 일치 → LPS[2] = 1
  4. “ABAB”: 접두사 “A”, “AB”, “ABA”, 접미사 “BAB”, “AB”, “B” → “AB” 일치 → LPS[3] = 2
  5. “ABABA”: 접두사 “A”, “AB”, “ABA”, “ABAB”, 접미사 “BABA”, “ABA”, “BA”, “A” → “ABA” 일치 → LPS[4] = 3
  6. “ABABAC”: 접두사 “A”, “AB”, “ABA”, “ABAB”, “ABABA”, 접미사 “BABAC”, “ABAC”, “BAC”,”AC”, “C” (일치하는 부분 없음) → LPS[5] = 0

➡ 최종 LPS 배열: [0, 0, 1, 2, 3, 0]


LPS 배열을 활용한 KMP 알고리즘 검색 방식

텍스트 "ABABDABACDABABCABAB"에서 "ABABCABAB"을 찾을 때, 비교 도중 불일치가 발생하면:

  • LPS 배열을 참고해 패턴을 적절히 이동 → 처음부터 다시 비교하지 않습니다

예를 들어,

  1. “ABABCABAB”의 6번째 문자 “C”에서 불일치 발생
  2. “C”의 LPS 값이 0이므로 패턴을 완전히 새로 비교
  3. 이후 “ABAB”에서 “B”와 불일치 발생 시, “B”의 LPS 값이 2 → 앞부분 2칸을 건너뛰고 다시 비교

LPS 배열 생성 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> computeLPS(string pattern) {
    int M = pattern.size();
    vector<int> lps(M, 0);
    int len = 0; // 현재까지 일치한 접두사의 길이
    int i = 1;   // 0번 인덱스는 항상 0이므로 1부터 시작

    while (i < M) {
        if (pattern[i] == pattern[len]) { // 접두사와 접미사가 같다면
            len++;
            lps[i] = len;
            i++;
        } else { // 불일치 발생
            if (len != 0) {
                len = lps[len - 1]; // 이전 LPS 값을 참고하여 이동
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

int main() {
    string pattern = "ABABAC";
    vector<int> lps = computeLPS(pattern);

    cout << "LPS 배열: ";
    for (int val : lps) {
        cout << val << " ";
    }
    return 0;
}


KMP알고리즘의 동작 과정

  1. 텍스트 T와 패턴 P를 비교하면서 진행한다.
  2. 불일치가 발생하면 LPS 값을 참고하여 점프한다.
  3. 패턴이 완전히 일치하면 시작 위치를 저장하고 계속 탐색한다.

장단점

장점

  • 빠른 검색 속도
    • 일반적인 브루트포스(Brute Force) 알고리즘이 O(N × M) 인 것과 비교하면 O(N + M) 으로 훨씬 빠릅니다.
    • 특히 긴 텍스트에서 반복적인 패턴 검색이 필요한 경우 매우 유리합니다.
  • 불필요한 비교 최소화
    • 이전 비교 결과를 활용하여 패턴을 이동하기 때문에 중복된 비교를 하지 않습니다.
    • 예를 들어, “AAAAA” 같은 반복적인 패턴을 탐색할 때 성능이 극적으로 향상됩니다.
  • 텍스트 길이에 비례하는 성능
    • 패턴이 길어지더라도, 한 번 계산한 LPS 배열을 사용하므로 텍스트의 길이(N)에 비례하는 성능을 보장합니다.

단점

  • LPS 배열을 만드는 전처리 과정이 필요합니다
    • 일반적인 문자열 검색보다 구현이 복잡하고, 추가적인 O(M)의 전처리 비용이 발생합니다.
    • 짧은 패턴을 한두 번만 찾는 경우, 간단한 브루트포스 방식이 더 유리할 수도 있습니다.
  • 패턴이 너무 다양하면 효율성이 떨어질 수 있습니다.
    • LPS 배열은 패턴의 자기 반복성(repetitive structure)을 활용하는 방식이므로, 패턴이 지나치게 불규칙한 경우(예: “XYZABC”), 점프 효과가 크지 않을 수 있습니다.
  • 메모리 사용량 증가
    • LPS 배열을 저장해야 하므로 O(M) 만큼의 추가 공간이 필요합니다. 다만,
    • 일반적으로 큰 문제는 아니지만, 메모리 사용이 중요한 환경에서는 고려해야 합니다.


시간 복잡도

  • 전처리 (LPS 배열 생성): O(M)
  • 검색 과정: O(N)
  • 총 시간 복잡도: O(N + M)

로, 브루트포스 O(N × M) 방법보다 훨씬 빠릅니다.

예제

#include <iostream>
#include <vector>
using namespace std;

// LPS 배열을 생성하는 함수
vector<int> computeLPS(string pattern) {
    int M = pattern.size();
    vector<int> lps(M, 0);
    int len = 0;
    int i = 1;

    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];  // 이전 LPS 값을 참고하여 이동
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP 검색 함수
void KMPSearch(string text, string pattern) {
    int N = text.size();
    int M = pattern.size();
    vector<int> lps = computeLPS(pattern);

    int i = 0, j = 0; // i: 텍스트 인덱스, j: 패턴 인덱스

    while (i < N) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == M) { // 패턴이 완전히 일치하는 경우
            cout << "패턴이 위치 " << i - j << "에서 발견됨\n";
            j = lps[j - 1]; // 다음 비교를 위해 LPS 값을 참고하여 이동
        } else if (i < N && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1]; // LPS 값만큼 이동
            } else {
                i++; // 일치하는 부분이 없으면 다음 문자로 이동
            }
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}



Top

You May Also Enjoy