지식과 경험, 기록을 위한 노트들

문자열 KMP 알고리즘 쉽게 알기

by · 2023-08-12

알고리즘은 컴퓨터 과학에서 가장 중요한 개념 중 하나입니다. 이 중에서도 KMP 알고리즘은 특히 문자열 매칭 문제를 효율적으로 해결하는 데에 사용되는 유명한 알고리즘입니다. 이 글에서는 KMP 알고리즘에 대해 쉽게 이해하고자 합니다. 또한 Java 예제 코드를 통해 실제 구현 방법도 알아보겠습니다. 그리고 메모리 사용량을 최소화하고 시간복잡도를 개선하는 방법에도 주목할 것입니다.



KMP 알고리즘이란?

KMP(Knuth-Morris-Pratt) 알고리즘은 하위 문자열을 검색하는 데에 사용되는 패턴 매칭 알고리즘입니다. 주어진 텍스트에서 특정 패턴을 찾는 문제는 많은 컴퓨터 애플리케이션에서 매우 흔하게 발생합니다. KMP 알고리즘은 이 문제를 해결하는 데에 효율적이며, 문자열 비교 연산의 수를 최소화하는 방법으로 동작합니다.



KMP 알고리즘의 구조

KMP 알고리즘의 핵심 아이디어는 “실패 함수”를 사용하는 것입니다. 실패 함수는 패턴 문자열의 각 위치에서 접두사와 접미사의 일치하는 길이를 저장하는 배열입니다. 이 배열을 사용하여 비교 연산을 최소화하고, 일치하지 않는 경우에도 텍스트 포인터를 적절한 위치로 이동시킵니다.







KMP 알고리즘의 구현 예제

이제 Java를 사용하여 KMP 알고리즘을 구현해보겠습니다.

public class KMPAlgorithm {
    public static int 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)) {
                j++;
                i++;
            }
            if (j == M) {
                return i - j;
            } else if (i < N && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i = i + 1;
                }
            }
        }
        return -1;
    }
  
    public static void computeLPSArray(String pattern, int M, int[] lps) {
        int len = 0;
        int i = 1;
        lps[0] = 0;
      
        while (i < M) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
  
    public static void main(String[] args) {
        String text = "ABCABCDABABCDABCDABDE";
        String pattern = "ABCDABD";
        int index = KMPSearch(text, pattern);
      
        if (index != -1) {
            System.out.println("패턴이 텍스트에서 인덱스 " + index + "에서 찾았습니다.");
        } else {
            System.out.println("패턴을 찾을 수 없습니다.");
        }
    }
}




KMP 알고리즘의 시간 복잡도

KMP 알고리즘은 텍스트를 한 번만 순회하며, 실패 함수를 미리 계산한 후 사용하기 때문에 시간복잡도가 O(N+M)입니다. 여기서 N은 텍스트 길이이고, M은 패턴 길이입니다. 따라서 KMP 알고리즘은 매우 효율적인 문자열 매칭 알고리즘이라고 할 수 있습니다.



마무리

KMP 알고리즘은 효율적인 문자열 매칭을 위한 알고리즘으로, 특히 대용량 텍스트에서 패턴을 검색하는 경우에 유용합니다. 이 알고리즘은 실패 함수와 텍스트, 패턴 포인터를 이용하여 일치하지 않는 위치에서도 연산을 최소화하도록 설계되었습니다. 따라서 메모리 사용량을 최소화하고 시간복잡도를 개선하는 효과적인 알고리즘입니다.

더 자세한 내용은 링크에서 확인할 수 있습니다.

You may also like...