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

Question

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

Редакция 1

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

Answer 1

Хм, звучит как двумерная версия сопоставления строк. Интересно, есть ли 2D-версия Бойера-Мура?

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

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

Answer 2

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

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

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

Answer 3

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

• http://www.springerlink.com/content/96511486841752h4/
• http://www.springerlink.com/content/e65lt4r77773l29g/

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

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

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

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