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?¿Cuál es la forma más rápida de 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".
- En el primer pase, encuentre todas las apariciones del primer caracter y almacene sus posiciones.
- 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.
Depende. Si tiene la cadena "aaaaaa", ¿cuántos "aa" hay? 3? 5? También depende del idioma que estés usando. – Peter