¿Cuál es la forma más rápida de encontrar todas las apariciones de una subcadena?

Question

Esto es puramente por curiosidad. Estaba revisando un artículo que comparaba varios algoritmos de búsqueda de cadenas y noté que todos estaban diseñados para encontrar la primera subcadena correspondiente. Esto me hizo pensar ... ¿Qué pasaría si quisiera encontrar todas las apariciones de una subcadena?

Estoy seguro de que podría crear un bucle que utilizara una variante de KMP o BM y descartara cada aparición encontrada en una matriz, pero esto difícilmente parece ser el más rápido.

¿No sería superior un algoritmo de divide y vencerás?

Por ejemplo, digamos que busca la secuencia "abc" en una cadena "abbcacabbcabcacbccbabc".

1. En el primer pase, encuentre todas las apariciones del primer caracter y almacene sus posiciones.
2. En cada pase adicional, use las posiciones del pase anterior para encontrar todas las apariciones del próximo carácter, reduciendo los candidatos para el próximo pase con cada iteración.

Teniendo en cuenta la facilidad con la que se me ocurrió esta idea, supongo que alguien ya se le ocurrió y la mejoró hace 30 años.

Answer 1

No existe una única "forma más rápida" que depende de

A) ¿Qué es realmente la cadena de construir (longitud, distribución carácter, ...)

B) en el que el hardware esta corre

C) Si desea que todos los resultados en forma paralela o secuencial

D) otros parámetros (por ejemplo, se encuentran los elementos se superponen, busca una o varias veces)

E) Si ve esta implementación específica o simplemente académica. En la implementación, hay muchas formas adicionales de optimizar cosas. P.ej. el almacenamiento temporal (como en su sugerencia) a menudo es muy costoso.

La idea que tiene, por ejemplo, destruiría por completo cualquier caché de la CPU para cadenas largas. Entonces sería MUY lento en esos casos.

Answer 2

Ver Suffix array

Aplicaciones

la matriz sufijo de una cadena pueden ser utilizados como un índice para localizar rápidamente cada aparición de una subcadena dentro de la cadena. Encontrar cada aparición de la subcadena es equivalente a encontrar cada sufijo que comience con la subcadena. Gracias al orden lexicográfico , estos sufijos se agruparán en el conjunto de sufijos, y se pueden encontrar de manera eficiente con una búsqueda binaria. Si se implementó directamente, esta búsqueda binaria toma el tiempo O (mlogn), donde m es la longitud de la subcadena .Para evitar la repetición de las comparaciones , las estructuras de datos adicionales dando información sobre los prefijos comunes más largos (LCP) de los sufijos son construidos, dando O (m + logn) búsqueda tiempo.

Answer 3

Si solo está procesando una cadena dada una vez, la matriz de sufijo es excesiva. Se necesita tiempo para crear O (n log n), por lo que un algoritmo de estilo KMP lo superará. Además, si la cadena es enorme o si desea obtener resultados en tiempo real a medida que recibe la cadena, la matriz de sufijos no funcionará.

Sin duda es posible modificar el algoritmo KMP para continuar después de encontrar una coincidencia sin tomar memoria adicional, además de la memoria utilizada para almacenar las coincidencias (que también puede ser innecesaria, si simplemente está imprimiendo coincide o los procesa a medida que avanza). Como punto de partida, tomar el Wikipedia implementation y modificar el estado de "retorno m" a "añadir m a una lista de índices". Pero aún no has terminado. También debe preguntarse, ¿permite ocurrencias superpuestas? Por ejemplo, si su subcadena es "abab" y está buscando en la cadena principal "abababab", ¿hay dos ocurrencias o tres? En el ejemplo que di ("como punto de partida"), se puede o bien restablecer i a 0 para dar el "dos" respuesta, o podría caer a través de la caja "de otro modo" después de la "m añadir" para dar las "tres " responder.

Answer 4

Tanto KMP y BM fácilmente se pueden utilizar para encontrar varias coincidencias también. También recomendaría el uso de Rabin-Karp, que en mi humilde opinión es más fácil de entender, pero no es realmente tan rápido para varios partidos (O (n + k m *) Creo, donde n es la longitud del texto, m es la longitud del patrón y k es el número de ocurrencias). Pero es fácil de modificar tanto para las coincidencias superpuestas como para las que no se solapan.

También se puede hacer uso de árboles de sufijo/sufijo arrays, pero son más difíciles de código y en realidad no comprar cualquier aumento de la velocidad.