Algoritmo para contar las ocurrencias de una matriz dentro de una más grande

Question

me estoy enfrentando un problema en este momento, necesito contar el número de veces que aparece una determinada matriz MxM dentro de una NxN (esta debe ser más grande que la primera) ¿Alguna pista sobre cómo hacer esto? Voy a implementarlo en C y no hay opción para cambiarlo.

Revisión 1

Hola a todos, me gustaría decir gracias a todas las respuestas y opiniones sobre el asunto. Debo decirles que después de muchas horas de duro trabajo hemos llegado a una solución que no es estrictamente como el enfoque de Boyer-Moore, sino más bien un algoritmo por mi cuenta. Estoy planeando publicarlo una vez que haya sido probado y terminado. Las soluciones ahora se están adaptando para ser paralelizadas para la optimización de velocidad utilizando el clúster universitario con la biblioteca C MPI.

Answer 1

Hm, parece una versión bidimensional de la coincidencia de cadenas. Me pregunto si hay una versión 2D de Boyer-Moore.

A Boyer-Moore Approach for Two-Dimensional Matching

Ah, aparentemente existe. :-)

Answer 2

Un enfoque que inmediatamente vino a la mente:

Tratar la matriz grande como una cadena lineal de "personajes" N * N y la pequeña matriz como una expresión regular lineal de longitud (M + 1) * M con "caracteres literales" en las primeras M posiciones de cada "fila" y el equivalente de .{N-M} en la posición restante de cada fila. Compile la expresión regular a un DFA y ejecútelo.

El tiempo para encontrar todas las coincidencias es O (N * N). Sospecho que hay algoritmos más elegantes que funcionarían (adaptaciones de algoritmos de búsqueda de subcadenas de 1-d más elegantes), pero este no es tan malo.

Answer 3

Recientemente, se han desarrollado algoritmos rápidos para construir árboles de sufijos 2D. Éstos se pueden utilizar para encontrar cualquier submatriz cuadrada en una matriz más grande en el tiempo independiente del tamaño de la matriz más grande:

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

Es posible que tenga que ser suscriptor para ver esos papeles.

También me pareció que éste era de libre acceso, que describe un algoritmo de construcción aleatorio que es espera lineales de tiempo:

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

espero que la construcción de un árbol de sufijos 2D y búsqueda con eso sería más rápido si necesita buscar muchas submatrices diferentes en una sola matriz, pero es probable que sea más lento que Boyer-Moore 2D si va a buscar dentro de una matriz diferente cada vez.