라빈 카프(Rabin-Karp), Hash 기반으로 문자열 빨리 찾기

---

라빈 카프 알고리즘은 hash 알고리즘을 기반으로 하고 있기 때문에 hash 알고리즘은 밑에 링크에서 다루도록 하겠습니다.

Hash 알고리즘

라빈카프 알고리즘은 서로 다른 두 문자열을 비교시에 두 문자열의 해시 코드로 일치 여부를 판단하는 알고리즘 입니다.

​

​

1. 문자열 순차 탐색

긴글에서 특정 패턴에 해당하는 문자열을 비교 할때 어떻게 비교를 할까요?

찾고자 하는 문자열의 길이 N을 전체 문자열의 길이 M번 만큼 반복 해야 하기 때문에 시간 복잡도는 O(MN)에 해당 합니다.

​

​

2. 라빈 카프(Rabin-Karp) 원리

패턴을 찾기 위해서 탐색을 하는데, 패턴의 hash 코드와 비교 하는 문자열의 hash 코드만을 비교 하고 hash 코드가 같다면 그때 순차 비교를 하여 전체 문자열에서 원하는 패턴의 문자열을 찾을 수 있습니다.

​

​

3. 라빈카프의 hash 함수

라빈카프 알고리즘에서 중요한 것 중 하나가 hash 함수 입니다.

각 자리의 해당하는 문자를 ASCII 코드로 변환하여 2의 거듭제곱을 곱하여 각 문자의 해당하는 값을 더하여 계산 합니다.

​

​

4. 라빈 카프 hash 함수의 트릭

라빈 카프 알고리즘의 특징은 문자열이 연속적인 것을 이용하는 것 입니다. 먼저 처음 문자열에 hash 코드를 구해 놓고 그 다음은 맨앞에 문자를 빼주고 그 다음 문자를 더해 주는 식으로 hash 코드를 계산 할 수 있습니다. 그 다음 문자들의 hash 코드를 계산 할때는 2를 곱해주어 한칸씩 이동하는 효과를 줄 수가 있습니다.

​

​

5. JAVA 코드

import java.util.ArrayList;
import java.util.List;

public class RabinKarp {
    public static void main(String[] args) {
        String parent = "abaaccdaabacaba";
        String pattern = "accdaa";
        List<Integer> list = new Solution().solve(parent, pattern);
        for (Integer value : list) {
            System.out.printf("%d번째에서 발견했습니다.", value);
            System.out.println();
        }
    }
}

class Solution {
    List<Integer> solve(String parent, String pattern) {
        double parentHash = 0, patternHash = 0, power = 1;
        int parentLen = parent.length();
        int patternLen = pattern.length();
        // 패턴이 일치하는 위치를 저장할 리스트
        List<Integer> findedList = new ArrayList<>();

        for (int i = 0; i < parentLen - patternLen; i++) {
            if (i == 0) {
                // 전체 문자열에 첫 파트의 hash 코드 구하기
                // 패턴 문자열 hash 코드 구하기
                for (int j = 0; j < patternLen; j++) {
                    parentHash = parentHash + parent.charAt(patternLen - 1 - j) * power;
                    patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power;
                    if (j < patternLen - 1) power = power * 2;
                }
            } else {
                // 긴글 해시 값 = 2 * (첫파트 해시 값 - 가장 앞에 있는 문자) + 새롭게 들어온 문자
                parentHash = 2 * (parentHash - (parent.charAt(i - 1) * power)) + parent.charAt(patternLen - 1 + i);
            }

            if (parentHash == patternHash) {
                // hash 코드가 같아도 문자열이 다를 수 있기 때문에 (충돌)
                // 다시 한번 문자열이 맞는지 검사 한다.
                boolean finded = true;
                for (int j = 0; j < patternLen; j++) {
                    if (parent.charAt(i + j) != pattern.charAt(j)) {
                        finded = false;
                        break;
                    }
                }
                if (finded) {
                    findedList.add(i + 1);
                }
            }
        }
        return findedList;
    }
}