Как включить мод в скользящий хэш алгоритма Рабина Карпа?

Question

Я пытаюсь реализовать алгоритм Рабина Карпа с мод.Хэш-функция, которую я использую:

H1= c1*a^k-1 + c2*a^k-2 +c3*a^k-3 +…+ck*a^0

Здесь cx - значение ASCII символа.И чтобы бросить его, я сначала отбрасываю первый член, вычитая его, затем умножаю на a и добавляю новый термин, умножая его на ^ 0.

Теперь проблема в том, чтобы иметь дело с большими значениями, которые я использовал модоперации, но, делая это, я не могу правильно его свернуть.Мой код выглядит следующим образом:

public class RabinKarp {
private static final int base = 26;
private static final int mod = 1180637;

public static void main(String[] args) {
    String text = "ATCAAGTTACCAATA";
    String pattern = "ATA";
    char[] textArr = text.toCharArray();
    char[] patternArr = pattern.toCharArray();
    System.out.println(getMatchingIndex(textArr, patternArr));
}

public static int getMatchingIndex(char[] textArr, char[] patternArr) {
    int n = textArr.length;
    int m = patternArr.length;
    int patternHash = getHashForPatternSize(patternArr, m);
    int textHash = getHashForPatternSize(textArr, m);
    for(int i = 0; i < n-m; i++) {
        if(patternHash == textHash && checkMatch(textArr, patternArr, i, m))
            return i;
        textHash = rollingHash(textArr, textHash, i, m);    
    }
    return -1;
}

public static boolean checkMatch(char[] textArr, char[] patternArr, int i, int m) {
    for(int j = 0; j < m; j++,i++) {
        if(textArr[i] != patternArr[j])
            return false;
    }
    return true;
}

public static int rollingHash(char[] textArr, int textHash, int i, int m) {
    return (textHash * base - modularExponentiation(base, m, mod) * (int)textArr[i] + (int) textArr[i+m])%mod;
}

public static int getHashForPatternSize(char[] arr, int m) {
    int hash = 0;
    for(int i = 0, p = m; i < m; i++, p--) {
        hash = (hash%mod + calcHash(arr[i], p)%mod)%mod;
    }
    return hash;
}

public static int calcHash(char alphabet, int p) {
    return (((int) alphabet)%mod * modularExponentiation(base, p, mod)%mod)%mod;
}

public static int modularExponentiation(int base, int p, int mod) {
    if(p == 0)
        return 1;
    if(p%2 == 0)
        return modularExponentiation((base*base)%mod, p/2, mod);
    else
        return (base*modularExponentiation((base*base)%mod, (p-1)/2, mod))%mod;
}
}

Проблема в том, что textHash и patternHash не совпадают ни в одной точке.Я уверен, что проблема с модом операций.Может кто-нибудь сказать, как иметь мод, а также правильно использовать катящийся хеш.Я был бы очень благодарен.

Answer 1

Обычный способ вычисления скользящего хэша Рабина-Карпа состоит в том, чтобы рассматривать символы в порядке с прямым порядком байтов, а не ваше решение с прямым порядком байтов.Это значительно упрощает арифметику, поскольку позволяет избежать деления.Модульное деление нетривиально, и вы не можете просто реализовать его как (p/q)%b.

Если мы возьмем скользящий хеш как

H<sub>0&hellip;k-1</sub> = (c<sub>0</sub>*a<sup>k-1</sup> + c<sub>1</sub>*a<sup>k-2</sup> + c<sub>2</sub>*a<sup>k-3</sup> &hellip;+&hellip; c<sub>k-1</sub>*a<sup>0</sup>) mod b

Тогда следующий член будет:

H<sub>1&hellip;k</sub>   = (         c<sub>1</sub>*a<sup>k-1</sup> + c<sub>2</sub>*a<sup>k-2</sup> &hellip;+&hellip; c<sub>k-1</sub>*a<sup>1</sup> + c<sub>k</sub>*a<sup>0</sup>) mod b

И мы можем легко увидеть, что

H<sub>1&hellip;k</sub>   = (a * H<sub>0&hellip;k-1</sub> - c<sub>0</sub>*a<sup>k</sup> + c<sub>k</sub>) mod b

Если мы затем вычислим m == a<sup>k</sup> mod b, то получится:

H<sub>1&hellip;k</sub>   = (a * H<sub>0&hellip;k-1</sub> - m * c<sub>0</sub> + c<sub>k</sub>) mod b

, что значительно меньше работает на каждой итерации и делаетне зависит от деления вообще.