Fendre la chaîne en mots

Une implémentation pseudocode, exploitant le fait que chaque partie de la chaîne doit être un mot, nous ne pouvons rien ignorer. Nous travaillons en avant à partir du début de la chaîne jusqu'à ce que le premier bit soit un mot, puis générer toutes les combinaisons possibles du reste de la chaîne. Une fois que nous avons fait cela, nous continuons à aller jusqu'au bout d'autres possibilités pour le premier mot, etc.

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    
}

Utilisez un Arbre préfixe pour votre liste de mots connus. Probablement libs comme myspell le faire déjà. Essayez d'utiliser un prêt-fait.

Une fois que vous avez trouvé une correspondance (par exemple, une «voiture»), divisez votre calcul: une branche commence à rechercher un nouveau mot («pourri»), une autre continue à explorer des variantes de début de début («carotte»).

efficacement, vous maintenez une file d'attente de paires (start_position, courant_position) de compensations dans votre chaîne chaque fois que vous divisez le calcul. Plusieurs threads peuvent apparaître de cette file d'attente en parallèle et essayer de continuer un mot qui commence à partir de start_position et est déjà connu jusqu'à actuel_position de la paire, mais ne s'arrête pas là. Lorsqu'un mot est trouvé, il est rapporté et une autre paire est apparue de la file d'attente. Quand c'est impossible, aucun résultat n'est généré. Lorsqu'une scission survient, une nouvelle paire est ajoutée à la fin de la file d'attente. Initialement, la file d'attente contient un (0,0) .