문자열 처리 알고리즘(1) - KMP 알고리즘 개념, 원리, 시간복잡도, 장단점, 주의점, C,Java,Python 예시코드

문자열 처리 - kmp 알고리즘

 

 

문자열 검색은 코딩 테스트에 꽤 자주 나오는 유형입니다.  KMP(Knuth-Morris-Pratt) 알고리즘은 이러한 문자열 검색 문제를 효율적으로 해결할 수 있도록 설계된 알고리즘입니다. 이번 포스팅에서는 KMP 알고리즘의 개념, 동작 원리, 시간 복잡도, 장단점, 구현 예제 등을 상세히 다루겠습니다.

---

 

 

1. KMP 알고리즘의 개념

 

KMP 알고리즘은 주어진 텍스트(text)에서 특정 패턴(pattern)을 효율적으로 찾는 방법을 제공합니다. 일반적인 탐색 방법은 모든 위치에서 패턴과 텍스트를 비교하지만, KMP는 "중복 작업"을 피하면서 효율성을 극대화합니다.

핵심 아이디어는 패턴의 접두사(prefix)와 접미사(suffix) 정보를 미리 계산해 활용하는 것입니다. 이를 통해 불필요한 비교를 줄일 수 있습니다.

---

반응형

 

 

2. 동작 원리

KMP 알고리즘은 두 단계로 구성됩니다:

 

(1) 패턴 전처리 단계

부분 일치 테이블(partial match table) 또는 lps 배열(longest prefix suffix)을 생성합니다. 이 배열은 패턴에서 접두사와 접미사가 일치하는 최대 길이를 저장합니다.

여기서 접두사(prefix)는 문자열의 시작부터 특정 위치까지의 부분 문자열이며, 접미사(suffix)는 문자열의 끝에서부터 특정 위치까지의 부분 문자열입니다. 중요한 점은 이 접두사와 접미사가 패턴 내에서 서로 겹치지 않으면서 동일해야 한다는 것입니다.

예시: 패턴 "ABABCABAB"

문자위치(i)	해당 위치의 문자	접두사	접미사	lps[i]
0	A	없음	없음	0
1	B	없음	없음	0
2	A	없음	없음	0
3	B	A	A	1
4	C	AB	AB	2
5	A	없음	없음	0
6	B	A	A	1
7	A	AB	AB	2
8	B	ABA	ABA	3

여기서 lps[i]는 문자 위치 i까지의 패턴에서 자신을 포함하지 않는 접두사와 접미사의 최대 길이를 나타냅니다.

 

더 쉬운 이해를 위한 예제:

패턴이 "AAACAAAA"라고 가정하겠습니다. 여기서 접두사와 접미사는 다음과 같이 계산됩니다:

i	문자 위치 i까지의 패턴	접두사	접미사	공통 길이
0	A	-	-	0
1	AA	A	A	1
2	AAA	AA	AA	2
3	AAAC	AAA	AAC	0
4	AAACA	A	A	1
5	AAACAA	AA	AA	2
6	AAACAAA	AAA	AAA	3
7	AAACAAAA	AAA	AAA	3

이 과정에서 lps 배열은 [0, 1, 2, 0, 1, 2, 3, 3]로 만들어집니다.

 

(2) 텍스트 탐색 단계

텍스트에서 패턴을 비교하면서, 불일치가 발생하면 lps 배열을 참고해 점프할 위치를 결정합니다.

 

예시: 텍스트 "ABABDABACDABABCABAB"에서 패턴 "ABABCABAB" 검색

1. 텍스트의 첫 번째 문자부터 세 번째 문자 "ABA"는 패턴과 일치.
2. 네 번째 문자 "D"에서 불일치 발생.
   • lps 배열에 따라 점프하여 비교를 재개 (패턴의 첫 번째 문자로 이동).
3. 계속 탐색하며 패턴이 텍스트의 마지막 부분에서 완전히 일치.

---

 

 

3. KMP 알고리즘의 시간 복잡도

1. 패턴 전처리: O(m) (m은 패턴의 길이)
2. 텍스트 탐색: O(n) (n은 텍스트의 길이)

전체 시간 복잡도는 O(n + m)으로, 매우 효율적입니다.

---

 

4. 장단점

장점:

• 중복 비교를 피하면서 빠르게 탐색 가능
• 텍스트의 크기에 비례한 선형 시간 복잡도를 가짐

단점:

• 패턴 전처리 단계에서 추가 메모리(lps 배열)가 필요함
• 단순한 패턴의 경우 오히려 구현이 복잡할 수 있음

---

 

5. 주의점

• 패턴이 길수록 lps 배열 생성 비용이 증가합니다. 따라서 짧은 패턴에서는 단순 비교가 더 나을 수도 있습니다.
• 올바르게 작성된 lps 배열이 효율성의 핵심입니다.

---

 

6. KMP 알고리즘의 구현

C 언어 구현

#include <stdio.h>
#include <string.h>

void computeLPSArray(char* pattern, int m, int* lps) {
    int length = 0;
    lps[0] = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearch(char* text, char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    int lps[m];
    computeLPSArray(pattern, m, lps);

    int i = 0, j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

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

 

Java 구현

public class KMP {

    // LPS (Longest Prefix Suffix) 배열 생성
    void computeLPSArray(String pattern, int m, int[] lps) {
        int length = 0; // 접두사와 접미사가 일치하는 길이
        int i = 1;
        lps[0] = 0; // 첫 번째 값은 항상 0

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }

    // KMP 알고리즘으로 패턴 검색
    void KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        int[] lps = new int[m];
        computeLPSArray(pattern, m, lps);

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

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";

        KMP kmp = new KMP();
        kmp.KMPSearch(text, pattern);
    }
}

 

 

 

Python 구현

def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps


def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    lps = compute_lps(pattern)

    i = 0  # index for text
    j = 0  # index for pattern
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1


# 실행 예제
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)