Алгоритм для подсчета вхождений матрицы в большую

Я столкнулся с проблемой прямо сейчас, мне нужно подсчитать количество времени, когда определенная матрица MxM появляется внутри NxN (она должна быть больше первой). Любые подсказки о том, как это сделать? Я собираюсь реализовать его в C, и нет возможности изменить его.

Версия 1

Приветствую всех, я бы очень хотел поблагодарить всех ответов и мнений по этому вопросу. Я должен сказать вам, что после многих часов напряженной работы мы пришли к решениям, которые не совсем похожи на подход Boyer-Moore, а скорее на алгоритм. Я планирую опубликовать его, как только он будет протестирован и закончен. В настоящее время решения адаптируются к параметризации для оптимизации скорости с использованием университетского кластера с библиотекой C Library.

Ответ 1

Hm, звучит как двухмерная версия соответствия строк. Интересно, есть ли 2D-версия Boyer-Moore?

Подход Бойер-Мура для двумерного соответствия

А, видимо, есть.: -)

Ответ 2

Один подход, который сразу пришел в голову:

Рассматриваем большую матрицу как линейную строку из N * N "символов" и малую матрицу как линейное регулярное выражение длины (M + 1) * M с "буквальными символами" в первых M положениях каждой строки "и эквивалент .{N-M} в остальном положении каждой строки. Скомпилируйте регулярное выражение в DFA и запустите его.

Время нахождения всех совпадений - O (N * N). Я подозреваю, что есть более удобные алгоритмы, которые будут работать (адаптация алгоритмов поиска подстроки 1-го уровня fancier 1), но это не так уж плохо.

Ответ 3

Недавно были разработаны быстрые алгоритмы для построения 2D суффикс-деревьев. Они могут быть использованы для нахождения любой квадратной подматрицы в большей матрице во времени, не зависящей от размера большей матрицы:

Возможно, вам понадобится подписчик, чтобы увидеть эти документы.

Я также нашел это свободно доступное, которое описывает рандомизированный алгоритм построения, который ожидается линейным временем:

http://www.cs.nyu.edu/cs/faculty/cole/papers/CH00.ps

Я ожидаю, что построение дерева суффиксов 2D и поиск с ним будут быстрее, если вам нужно искать множество разных подматриц в одной матрице, но, вероятно, медленнее, чем 2D Boyer-Moore, если вы будете искать в другом матрица каждый раз.