[java] 자바에서 사용하는 KMP 알고리즘

15 Dec 2023

java

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색 알고리즘 중 하나로, 특정 패턴을 찾는 데 사용됩니다. 이 알고리즘은 특정 텍스트에서 특정 패턴을 효율적으로 찾아내는 데 사용됩니다. KMP 알고리즘을 사용하면 문자열 검색 속도를 향상시킬 수 있습니다.

KMP 알고리즘의 동작

KMP 알고리즘은 주어진 텍스트에서 패턴과 일치하는 부분을 찾기 위해 텍스트를 한 글자씩 이동하면서 비교해나갑니다. 이때, 패턴에서 일치하지 않는 부분이 발견되면, 그 일치하지 않는 위치부터 다시 비교를 시작하지 않고, 패턴의 앞 부분에서 일치하지 않은 부분과 일치하는 부분을 찾아 건너뛰는 방식으로 동작합니다.

KMP 알고리즘의 예시

public class KMPAlgorithm {
    public static int kmpSearch(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int textLength = text.length();
        int patternLength = pattern.length();
        int i = 0;  // 인덱스 i는 text를 순회하는 인덱스
        int j = 0;  // 인덱스 j는 pattern을 순회하는 인덱스
        while (i < textLength) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == patternLength) {
                System.out.println("패턴이 텍스트에서 인덱스 " + (i - j) + " 에서 발견되었습니다.");
                j = lps[j - 1];
            } else if (i < textLength && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;  // 패턴이 없을 경우 -1 반환
    }

    private static int[] computeLPSArray(String pattern) {
        int patternLength = pattern.length();
        int[] lps = new int[patternLength];
        int len = 0;
        int i = 1;
        lps[0] = 0;
        while (i < patternLength) {
            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++;
                }
            }
        }
        return lps;
    }
}

위의 코드는 자바에서 KMP 알고리즘을 구현한 예시입니다. KMP 알고리즘은 효율적인 패턴 검색을 위해 LPS(Longest Proper Prefix which is also Suffix) 배열을 사용하여 패턴 일치의 위치를 찾아냅니다.

KMP 알고리즘은 문자열 검색 알고리즘 중 성능이 우수한 알고리즘 중 하나입니다. 이 알고리즘을 사용하면 대용량의 텍스트에서 원하는 패턴을 효율적으로 찾을 수 있습니다.

KMP 알고리즘의 동작

KMP 알고리즘의 예시

참고 자료