문자열 알고리즘 - KMP와 Robin-Karp 알고리즘

|  관련 강의 영상

https://www.youtube.com/watch?v=UcjK_k5PLHI 

- KMP나 Robin-Karp를 사용하면 O(n)의 시간복잡도로 문자열에서 패턴 문자열을 찾을 수 있다.

- KMP는 어려워서 일단 Robin-karp 부분만 찾아서 적용해보았다.

 

|  Robin-Karp 알고리즘 사용해보기

https://joomn11.tistory.com/111?category=900637 

[알고리즘] 라빈 카프(Rabin-Karp)(문자열 탐색)(Rolling Hash)

public static int robinKarp(String parent, String pattern, int parentSize, int patternSize){

    int parentHash = 0, patternHash = 0, power = 1;
    int result = 0;

    // 슬라이딩 윈도우 방식으로 하나씩 증가
    for (int i = 0; i <= parentSize - patternSize; i++) {
        // 처음에는, 패턴 문자열 길이만큼 해시값을 구한다.
        if (i == 0) {
            for (int j = 0; j < patternSize; j++) {
                parentHash += parent.charAt(j) * power;
                patternHash += pattern.charAt(j) * power;
            }

            if (i < patternSize - 1) {
                power *= 2;
            }
        } 
        // 처음이 아닌 경우, 가장 앞의 문자를 빼고, 새로운 문자를 추가한다.
        else {
            parentHash = (parentHash - parent.charAt(i - 1) * power) * 2
                    + parent.charAt(i + patternSize - 1);
        }

        // 윈도우 위치에서 부모와 패턴이 일치하는 경우
        if (parentHash == patternHash) {
            result++;
        }
    }

    return result;
}