Hashcode Рабина-Карпа слишком велик

Question

Как бороться с большим значением хеш-кода в алгоритме Рабина-Карпа с переменным хешем? Я использую модульную арифметику, чтобы избежать отрицательного числа, однако есть проблема, когда хеш-код превышает мое число по модулю (N = 83559671). Я установил для моего базового числа простое число (число для вычисления хэш-кода), а также число по модулю (действительно большое), но оно не работает с длинной строкой. Кто-нибудь может увидеть проблему?

Вот мой код

   public static void main(String [] args){

       int P = 13;         // base
       long M = 83559671;
       long iHash = 0;    
       String word = "abcbadccaaaabbbb";
       int WINDOW = 9;

       for(int i = 0; i < WINDOW; i++){
            iHash = int_mod(int_mod(iHash*P, M) + word[i], M);
       }

       for(int i = WINDOW; i < word.length; i++){
            iHash = int_mod(iHash - word[i-WINDOW] * get_pow(P, WINDOW-1, M), M);
            iHash = int_mod(iHash * P, M);
            iHash = int_mod(iHash + word[i], M);
       }

   }
   public static long get_pow(int p, int t, long M){
        long a = 1;
        for(int i = 0 ; i < t; i++){
              a = int_mod(a * p, M);
        }
        return a;
   }

   public static long int_mod(long a, long b){
        return (a % b+ b) % b;
   }

Проблема в том, что когда длина строки превышает 8, тогда хеш-код строки превышает значение по модулю 83559671, и это приводит к неправильному ответу при сравнении. Любые более короткие строки работают правильно.

Answer 1

Вам не нужно делать модуль вообще. Вот демо:

public class Foo {
  private static int hash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
      hash *= 31;
      hash += s.charAt(i);
    }
    return hash;
  }

  public static void main(String[] args) {
    String s1 = "abcdefghij";
    String s2 = s1.substring(1) + "k";
    int pow = 1;
    for (int i = 0; i < s1.length(); i++) {
      pow *= 31;
    }
    System.out.printf("hash(%s) = %d%n", s1, hash(s1));
    System.out.printf("hash(%s) = %d%n31 * hash(%s) - (31^%d * %s) + %s = %s%n",
        s2,
        hash(s2),
        s1,
        s1.length(),
        s1.charAt(0),
        s2.charAt(s2.length() - 1),
        31 * hash(s1) - (pow * s1.charAt(0)) + s2.charAt(s2.length() - 1));
  }
}

Это (правильно) распечатывает:

hash(abcdefghij) = -634317659
hash(bcdefghijk) = 21611845
31 * hash(abcdefghij) - (31^10 * a) + k = 21611845

Answer 2

Почему бы вам не рассматривать вашу строку как полином? Предположим, у вас есть строка S длины n, Теперь взглянем на следующую функцию: F(x) = S[0]*x^(n-1) + S[1]*x^(n-2) + ... + S[i]*x^(n-i-1) + ... + S[n - 2]*x + S[n-1], Что произойдет, если вы попытаетесь вычислить F(P), где P база из вашего фрагмента кода? Ну, вы бы получили хэш строки Рабина-Карпа S, Но с тех пор F(x) является полиномом, мы можем использовать правило Хорнера для вычисления F(P), Результирующее значение может быть очень большим, поэтому мы используем модульную арифметику:

static final long M = 83559671;
static final int Base = 13;

static long hash(String s, int from, int to) {
    int iHash = 0;
    for(int i = from; i < to; i++) {
        iHash *= Base;
        iHash += s.charAt(i);
        iHash %= M;
    }
    return iHash;
}

Вы можете использовать эту функцию для получения хеша строки, которая будет найдена в тексте. И для начального окна в тексте. Затем вы можете сдвинуть окно и пересчитать хеш:

static void find(String pattern, String text) {
    if(text.length() < pattern.length()) return;
    int len = pattern.length();
    long ph = hash(pattern, 0, len);
    long h = hash(text, 0, len);
    long basePower = mpow(Base, len);

    if(h == ph) System.out.println("match at 0");
    for(int i = len; i < text.length(); i++) {
        h *= Base;
        h += text.charAt(i);
        h -= basePower * text.charAt(i - len);
        h = mod(h);
        if(h == ph) System.out.println("match at " + (i - len + 1));
    }
}

static long mod(long a) {
    a %= M;
    if(a < 0) {
        a += M;
    }
    return a;
}

static long mpow(long x, int k) {
    long result = 1;
    for(; k > 0; k >>= 1) {
        if(k % 2 == 1) {
            result = mod(result * x);
        }
        x = mod(x * x);
    }
    return result;
}

public static void main(String[] args) {
    find("abracadabra", "abracadabracadabra");
}

Для получения дополнительной информации об этом подходе я рекомендую обратиться к CLRS.