Est-ce qu'il existe un sous-ensemble de sous-chaînes pour reconstruire une autre chaîne?

Question

Je recherche un algorithme de haute performance pour vérifier si je peux reconstruire une chaîne donnée à l'aide d'un ensemble de substrings donné. Plus de détails:

Disons que nos chaînes sont sur l'alphabet $ \ sigma $ .

entrées :

• une chaîne $ s \ in \ sigma ^ * $
• Un jeu fini de chaînes $ a={a_1, a_2, ..., a_n \} \ sous-ensemble \ sigma ^ * $ .

sortie :

• si $ \ existe m: \ existez b_1, b_2, \ ldots, b_m \ in a: b_1 + b_2 + \ cdots + b_m= s $

où $ + $ est une concaténation de chaîne.

Par exemple, si $ s= {} $ " $ abcd $ " et $ a={$ " $ ab $ " $, $ < / span> " $ CD $ " $, $ " $ AC $ " $ \} $ , la réponse est vraie. Aux fins de cette question, supposons que les chaînes dans $ a $ peuvent être réutilisées plusieurs fois si nécessaire.

Answer 1

Si réutiliser des chaînes dans $ a $ est autorisé Vous pouvez le résoudre avec une programmation dynamique: première, stockez des chaînes dans $ A $ dans un arbre de préfixe (juste un arbre de suffixe inversé lien ), et Déttrmine récursivement si $ s [i: end] $ peut être construit à partir de $ A $ : laisse $ \ ell $ soit la longueur de la chaîne et wlog suppose $ s $ est ajouté par $ \ $$ et $ a \ obtient une \ tasse \ {\ $ \ \} $ . Morever, let $ m [i] \ in \ {0,1 \ \ \ \ {0,1 \ \ \ \ {0,1 \} $ indique si s [i: \ ell] $ peut être construit par des éléments dans $ a $ . Initialiser $ m [i] \ obtient \ gajt $ pour $ i= 0, \ dots, \ ell-1 $ < / span> et $ m [\ \ ell]= 1 $ (parce que $ s [\ eell]=$$ < / span>). Maintenant, supposons que $ f (i) $ est la fonction qui calcule de manière récursive $ m [i] $ si Il n'a pas déjà été calculé. Quand $ f (i) $ est appelé, commencez à la racine de l'arborescence de suffixe de $ a $ et traverse s [i], s [i + 1], \ dotes $ sur l'arbre suffixe jusqu'à l'index $ j $ , tel que le nœud correspondant est dans $ a $ et appelez de manière récursive $ f (j) $ . Si retourne 1 $ $ , définissez $ m [i]= 1 $ et retourner $ 1 $ . Sinon, répétez le processus avec parcroversion de $ s [j + 1], s [j + 2], \ points $ jusqu'à un autre membre de $ A $ A $ ou une feuille est atteinte. S'il n'y avait pas de succès, définissez $ m [i]= 0 $ et retourner $ 0 $ . Pour décider du problème, appelez $ F (1) $ . La plus grande complexité des cas est la complexité est $ \ ell d $ , avec $ d $ étant profondeur du Suffixe arbre (séquence la plus longue dans $ A $ ), ainsi que le coût de la construction de l'arbre de préfixe.

Le pire des cas dans de nombreux cas sera évité, car la recherche d'appel récursive s'arrête dès qu'une solution est trouvée. Donc, dans la pratique, la $ \ ell d $ peut être beaucoup moins moindre. La construction de l'arbre suffixe peut être coûteuse en fonction de $ a $ . Mais si $ a $ est utilisé pour plusieurs chaînes $ s $ , le coût est amorti. Si $ a $ est vraiment gros et $ s $ est court, il peut être préférable de bien trier des éléments de $ a $ et faire une recherche binaire au lieu de traverser.