Реализация алгоритма Рабина Карпа с использованием Rolling Hash в Java

Существует так много алгоритмов поиска по шаблону для строки. Алгоритм KMP, алгоритм Z, алгоритм Рабина Карпа и т. д. Эти алгоритмы являются оптимизацией алгоритма поиска наивного шаблона.

Наивный алгоритм поиска шаблона:

Input   :  "AABACACAACAC"
Pattern :  "CAC"
Output  :  [4,9]

AABACACAACAC

Реализация:

Объяснение вывода:

The above algorithm for pattern searching is the basic algorithm the worst as the average time complexity of this algorithm is O(n×m) where n is the pattern and m is the given string. 

Как мы можем уменьшить сложность этого алгоритма?

Это возможно с помощью прокатки хэша . Алгоритм Рабина-Карпа — это один из оптимизированных алгоритмов наивного алгоритма, который выполняет поиск путем перелистывания строки и поиска шаблона.

Иллюстрация:

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Процедура:

• Рассчитайте хеш-значение шаблона (путем создания собственной хеш-функции или уравнения для определения индивидуального хэш-значения для каждого символа)
• Перебрать строку, проверить хеш-значение каждой сгенерированной подстроки размера шаблона, если он совпал, проверить каждый символ шаблона, а также строку, если все совпали, напечатать начальный индекс строки.
• Если не совпадает, переходим к следующему символу, пропуская первый символ и добавляя хеш-значение следующего символа, мы не вычисляем хеш-значение следующей подстроки в строке, только сдвигаем окно, пропускаем первый символ и добавляем последний символ в окне путем вычисления его хеш-значения, т.е. скользящего хэша.

Реализация:

Алгоритм Simple Rolling, предполагающий паттерн длины 2

1. Инициализировать темп=4(1+3)
2. Сверните хеш-значение к следующему элементу.
3. Повторить цикл 'i' <= Array.length-pattern.length
4. Удалите первый элемент из переменной temp и добавьте следующий элемент в переменную temp. temp = temp-Array[i]+Array[i.pattern.length()]