Rabin karp

• 문자열 검색을 위해 해시 값 함수를 이용
• 패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
• 최악의 시간 복잡도는 $O(MN)$이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘

아이디어 설명

• 문자열 대신 숫자로 생각해 보자
• 10개의 숫자문자열이 주어지고 찾으려는 패턴은 “4321”이다
  

• 패턴의 해시 값을 계산한다
  • 각 자리의 숫자에 자리 값을 곱하여 더한다
  • 즉 $4 * 10^3 + 3 * 10^2 + 2 * 10 + 1 = 4321$
  • 해시 값은 “4321”라는 문자열이 아니라 정수 값 4321이 된다
• 찾고자 하는 문자열에서 4자리씩 해시 값을 계산한다
  

• 찾고자 하는 문자열에서 해시 값을 구할 때…
  - 찾고자하는 문자열에서 한 글자씩 이동하며 패턴 길이만큼 읽어서 해시 값을 계산하는 것이 아니라
  - 새로 추가되는 문자와 그전에 읽었던 값을 이용하여 해시 값을 구한다
  - 즉 아래 그림처럼 다음 해시 값을 구할 때 그 전의 해기 값을 이용한다
  

고려사항

• 처음 해시 값을 구할 때는 찾고자 하는 문자열에서 패턴 길이 만큼 읽어서 구한다
• 본 예제에서는 이해를 돕기 위해 패턴의 길이를 4자리 정수로 작게 했지만 패턴이 문자열이며 길이가 커지면 길이를 일정 자리수로 맞추기 위해 mod 연산을 취해 준다
• 따라서 해시 값이 일치하더라도 실제 패턴이 일치하지 않을 수 있기 때문에 해시 값이 일치하면 문자열 일치를 검사해야 한다 (이를 해시 충돌이라 한다)

package com.ssafy.strpattern;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class RabinKarp {
    static final long MOD = 1_000_000_009;   
    static final long base = 26;
    static long pHash, tHash, power = 1;
    static char[] text, pattern;
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        text = br.readLine().trim().toCharArray();
        pattern = br.readLine().trim().toCharArray();

        /*
            Rabin fingerprint
            -   라빈 카프 알고리즘에서 메이저하게 사용되는 해쉬 함수 기법
                hash = A0 + A1*b^1 + A2*b^2 + ...;
         */
        int tLen = text.length;
        int pLen = pattern.length;

        for (int i = 0; i < pLen; i++) {
            pHash = (pHash * base) % MOD;
            pHash = (pHash + pattern[i]) % MOD;
            tHash = (tHash * base) % MOD;
            tHash = (tHash + text[i]) % MOD;
            if(i < pLen -1){
                power = (power * base) % MOD;
            }
        }

        if(tHash == pHash){
            list.add(1);
        }

        for (int i = 1, end = tLen-pLen; i <= end; i++) {
            // window에서 맨 앞부분 빼고 맨 뒷부분 추가
            tHash = (((tHash - (text[i - 1] * power) % MOD + MOD) % MOD * base) % MOD + text[i + pLen - 1]) % MOD;
            if (tHash == pHash){
                list.add(i+1);
            }
        }

        System.out.println(list.size() + "개 일치");
        for (Integer i : list) {
            System.out.print(i + " ");
        }
    }
}