라빈-카프(Rabin-Karp)

문자열에 해싱기법을 사용해서 해시값으로 문자열을 비교하는 알고리즘

보통 문자열 매칭 알고리즘에 많이 쓰임 (특정 문자열 패턴이 원본 문자열에서 얼마나 나왔나?)

슬라이딩 윈도우와 비슷한 방식으로 rolling 기법을 사용해 문자열을 탐색하며, 기존의 문자열을 재활용하여 다음 문자열을 구함.

이때 소수 P와 a는 적당히 크게 잡아야하는데,

1. 너무 작으면 해쉬 충돌의 가능성
2. 너무 크면 오버플로우와 계산 시간의 증가

a진법을 사용하여 패턴과 원본 문자열들을 해싱.

정석: 적당히 큰 소수 P와 P의 원시근 a를 선언한 후, 문자열을 a진수로 나타냄(MOD P)

타협**: 적당히 큰 수 P, 소수 a를 선언. 해쉬충돌 방지를 위해 2~3 번의 해쉬 중첩 사용.**

 

예시 코드) BOJ 1786 찾기

import java.io.*;
import java.util.*;

public class Main {

    private static final int EXP1 = 251;
    private static final int EXP2 = 43;
    private static final long MOD = 1_000_000_005;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String in = br.readLine();
        String pattern = br.readLine();

        List<Integer> answer = solve(in, pattern);
        sb.append(answer.size()).append('\n');

        for (Integer integer : answer) {
            sb.append(integer).append(' ');
        }
        bw.write(sb.toString());
        bw.flush();

        br.close();
        bw.close();
    }

    private static List<Integer> solve(String in, String pattern){
        List<Integer> ret = new ArrayList<>();

        int inputLength = in.length();
        int patternLength = pattern.length();

        int inputHash1 = 0;
        int patternHash1 = 0;
        int inputHash2 = 0;
        int patternHash2 = 0;

        long power1 = 1;
        long power2 = 1;

        for(int i = 0; i <= inputLength - patternLength; i++){

            if(i == 0){

                for(int j = 0; j < patternLength; j++){
                    patternHash1 = (int) ((patternHash1 + (pattern.charAt(patternLength - j - 1) * power1)) % MOD);
                    inputHash1 = (int) ((inputHash1 + (in.charAt(patternLength - j - 1) * power1)) % MOD);

                    patternHash2 = (int) ((patternHash2 + (pattern.charAt(patternLength - j - 1) * power2)) % MOD);
                    inputHash2 = (int) ((inputHash2 + (in.charAt(patternLength - j - 1) * power2)) % MOD);

                    if(j < patternLength - 1){
                        power1 = (power1 * EXP1) % MOD;
                        power2 = (power2 * EXP2) % MOD;
                    }
                }
            }
            else{
                inputHash1 = (int) (((inputHash1 - in.charAt(i-1) * power1) * EXP1 + in.charAt(i + patternLength - 1)) % MOD);
                inputHash2 = (int) (((inputHash2 - in.charAt(i-1) * power2) * EXP2 + in.charAt(i + patternLength - 1)) % MOD) ;
                if(inputHash1 < 0) inputHash1 += MOD;
                if(inputHash2 < 0) inputHash2 += MOD;
            }
            if(inputHash1 == patternHash1
                && inputHash2 == patternHash2
            ) {
                ret.add(i + 1);
            }
        }
        return ret;
    }
}