Алгоритм Рабина Карпа для двумерных массивов

Question

Как расширить rabin karp для поиска шаблона mxm среди символов nxn?

Кто-нибудь может придумать псевдокод? И повлияет ли это на временную сложность алгоритма?

Answer 1

Один из подходов состоит из трех этапов:

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

2) Для каждого столбца используйте скользящий хеш Рабина-Карпа вниз по столбцу, чтобы взять значения хеш-функции, вычисленные на шаге (1) для непрерывных отрезков текста длины k, которые лежат непосредственно над и под друг другом, и вычислить комбинированное значение хеш-функции, которое соответствует к прямоугольнику текста.

3) Посмотрите на этот прямоугольник текста, как и раньше.

На шаге 2 мы начинаем со значений вида X[0] + X[1]*P + X[1]*P^2+..., полученных на шаге 1. Если вы используете множитель P^k для второго шаг, у вас должна получиться хеш-функция на прямоугольнике, идентичная той, что если вы переставили прямоугольник как одну строку и вычислили один длинный хэш Рабина-Карпа.

Как описано выше, вам нужно достаточно места для хранения хеш-значений для всех прямоугольных входных данных. Должно быть легко уменьшить это до достаточного количества хранилищ, чтобы держать прямоугольник хеш-значений, идущий вдоль входных данных, но идущий так же глубоко, как шаблон, который вы ищете. Возможно, вы могли бы сделать лучше, если бы вы сосредоточились на этом и сделали немного больше вычислений. Очевидно, что вы могли бы разделить регион до поиска за счет повторения квадратов вдоль границы вашего подразделения.