Esta es una entrevista question: Encuentre todas las subcadenas (en inglés) de una cadena determinada. (cada = cada, siempre, muy).Buscar todas las subcadenas (en inglés) de una cadena determinada
Obviamente, podemos recorrer todas las subcadenas y verificar cada una en un diccionario de inglés, organizado como un conjunto. Creo que el diccionario es lo suficientemente pequeño como para caber en la memoria RAM. ¿Cómo organizar el diccionario? Por lo que recuerdo, el comando original spell cargó el archivo words en un bitmap, representaba un conjunto de valores hash de palabras. Yo partiría de eso.
Otra solución es un trie construido a partir del diccionario. Usando el trie podemos recorrer todos los caracteres de cadena y verificar el trie para cada caracter. Supongo que la complejidad de esta solución sería la misma en el peor de los casos (O(n^2))
¿Tiene sentido? ¿Sugerirías otras soluciones?
Complejidad de bucle sobre todas las subcadenas comprobación de hashes depende de su cálculo hash - hay subcadenas Theta (n^2) de longitud promedio no O (1), por lo que necesita calcular un hash parcial que puede incrementar con un carácter a la vez para mantener O (n^2) en general. Lo mismo puede decirse de la búsqueda de trie o DAWG, por supuesto, desearía descender gradualmente comprobando todas las cadenas a partir de un punto determinado, pero probablemente sea más obvio que es lo correcto. –
Caminar por el trie, comenzando con cada posible carácter de inicio y emitir todas las palabras legales a medida que las encuentre parece bastante eficiente; dejas de buscar tan pronto como encuentras una secuencia de caracteres que no puede ser un prefijo de una palabra, y no puedes hacer mejor que O (n^2) - es posible que cada subcadena sea válida, y hay O (n^2) de esos. –