División de cadena en palabras

Question

Estoy buscando el algoritmo más eficiente para formar todas las combinaciones posibles de palabras de una cadena. Por ejemplo:

Input String: forevercarrot 

Output: 

forever carrot 
forever car rot 
for ever carrot 
for ever car rot 

(Todas las palabras deben ser de un diccionario).

Puedo pensar en un enfoque de fuerza bruta. (encuentre todas las subseries y coincidencias posibles) pero ¿cuál sería la mejor manera?

Answer 1

Implementación de psuedocode, explotando el hecho de que cada parte de la cadena debe ser una palabra, no podemos omitir nada. Avanzamos desde el inicio de la cadena hasta que el primer bit sea una palabra, y luego generamos todas las combinaciones posibles del resto de la cadena. Una vez que hayamos hecho eso, seguiremos adelante hasta que encontremos otras posibilidades para la primera palabra, y así sucesivamente.

allPossibleWords(string s, int startPosition) { 
    list ret 
    for i in startPosition..s'length 
     if isWord(s[startPosition, i]) 
      ret += s[startPostion, i] * allPossibleWords(s, i) 
    return ret  
} 

La pesadilla en este código es que usted va a terminar la repetición de cálculos - en su ejemplo, que va a terminar encima de tener que calcular allPossibleWords("carrot") dos veces - una vez en ["forever", allPossibleWords["carrot"]] y una vez en ["for", "ever", allPossibleWords["carrot"]]. Así que memorizar esto es algo a considerar.

Answer 2

Utilice un prefix tree para su lista de palabras conocidas. Probablemente libs como myspell ya lo hacen. Intente usar uno ya hecho.

Una vez que encuentre una coincidencia (por ejemplo, "automóvil"), divida su cálculo: una rama comienza a buscar una nueva palabra ("putrefacción"), otra continúa explorando variantes de inicio actual ("zanahoria").

Mantiene efectivamente una cola de pares (start_position, current_position) de desplazamientos en su cadena cada vez que divide el cálculo. Varios hilos pueden salir de esta cola en paralelo e intentar continuar una palabra que comienza desde start_position y ya se conoce hasta el current_position del par, pero no termina allí. Cuando se encuentra una palabra, se informa y se saca otro par de la cola. Cuando es imposible, no se genera ningún resultado. Cuando ocurre una división, se agrega un nuevo par al final de la cola. Inicialmente, la cola contiene un (0,0).

Answer 3

Consulte esta pregunta que tiene incluso mejores respuestas. Es un problema de programación dinámica estándar:

How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

Answer 4

cadena de entrada: forevercarrot

salida

:

siempre zanahoria siempre coche pudrición para siempre zanahoria para siempre la podredumbre coche programa

:

#include<iostream> 
#include<string> 
#include<vector> 
#include<string.h> 
void strsplit(std::string str) 
{ 
    int len=0,i,x,y,j,k; 
    len = str.size(); 
    std::string s1,s2,s3,s4,s5,s6,s7; 
    char *c = new char[len+1](); 
    char *b = new char[len+1](); 
    char *d = new char[len+1](); 
    for(i =0 ;i< len-1;i++) 
    { 
     std::cout<<"\n"; 
     for(j=0;j<=i;j++) 
     { 
      c[j] = str[j]; 
      b[j] = str[j]; 
      s3 += c[j]; 
      y = j+1; 
     } 
     for(int h=i+1;h<len;h++){ 
      s5 += str[h]; 
     } 
     s6 = s3+" "+s5; 
     std::cout<<" "<<s6<<"\n"; 
     s5 = ""; 
     for(k = y;k<len-1;k++) 
     { 
      d[k] = str[k]; 
      s1 += d[k]; 
      s1 += " "; 
      for(int l = k+1;l<len;l++){ 
      b[l] = str[l]; 
      s2 += b[l]; 
     } 
     s4 = s3+" "+s1+s2; 
     s7 = s4; 
     std::cout<<" "<<s4<<"\n"; 
     s3 = "";s4 = ""; 
     } 
     s1 = "";s3 = ""; 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    std::string str; 
    if(argc < 2) 
       std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n"; 
    else{ 
       str = argv[1]; 
       strsplit(str); 
    } 

return 0; 
}