Quelle est la meilleure structure de données et de l'algorithme pour comparer une liste de chaînes?

Question

Je veux trouver la plus longue séquence possible des mots qui correspondent aux règles suivantes:

• Chaque mot peut être utilisé au plus une fois
• Tous les mots sont des chaînes
• et la sa sb de deux peuvent être concaténées si les deux derniers caractères de sa correspondent aux deux premiers caractères de sb.

Dans le cas de la concaténation, elle est effectuée en faisant se chevaucher ces caractères. Par exemple:

• sa = "torino"
• sb = "Novare"
• sa concat sb = "torinovara"

Par exemple, je le fichier d'entrée suivante, "input.txt":

  

Novare

     

torino

     

Vercelli

     

ravenna

     

napoli

     

Liverno

     

messania

     

Novi Ligure

     

roma

Et, la sortie du fichier ci-dessus selon les règles ci-dessus doit être:

  

torino

     

Novare

     

ravenna

     

napoli

     

LIVOURNE

     

Novi Ligure

depuis la plus longue possible concaténation est:

torinovaravennapolivornovilligure

Quelqu'un peut-il s'il vous plaît aidez-moi avec ça? Quelle serait la meilleure structure de données pour cela?

Answer 1

Cela peut être présenté comme un problème de graphe orienté - les noeuds sont des mots, et ils sont reliés par un avantage si elles se chevauchent (et le plus petit recouvrement est choisie pour obtenir la plus longue), puis trouver le poids le plus élevé non chemin -intersecting.

(Eh bien, en fait, vous souhaitez étendre le graphique un peu pour gérer début et de fin à un mot. Un Adjoint « nœud de départ » avec un bord à chaque mot de longueur de poids mot / 2. Entre les mots, -overlap + finition / 2 + début de la longueur de longueur, et entre chaque mot et un « nœud de fin » « de mots de longueur / 2 ». Peut-être plus facile de le doubler.)

https://cstheory.stackexchange.com/questions/3684 / max-non-chevauchement-path-in-graphe pondéré

Answer 2

Je commencerais vraiment simple. Faire 2 vecteurs de chaînes, on normalement triés, un des 2 triés dernières lettres. Créer un index (vecteur d'entiers) pour le deuxième vecteur qui pointe sur la position de ce dans la première.

Pour le plus long .. d'abord supprimer les orphelins. mots qui ne correspondent pas à l'une des extrémités à quoi que ce soit. Ensuite, vous voulez construire un voisin de rejoindre arbre, c'est là que vous déterminez quels mots peuvent éventuellement atteindre l'autre. Si vous avez 2 ou plus d'arbres, vous devriez essayer le plus grand arbre en premier.

Maintenant, avec un arbre de votre travail consiste à trouver des extrémités qui sont rares, et les lier à d'autres fins, et répéter. Cela devrait vous obtenir une solution jolie belle, si elle utilise tous les mots de votre or, sauter les autres arbres. Si elle ne le fait pas alors votre dans toute une série d'algorithmes pour rendre cette efficacité.

Quelques points à considérer: Si vous avez des extrémités 3+ uniques vous garantis laisser tomber 1+ mots.     Cela peut être utilisé pour tailler vos essais jusqu'à la chasse pour une réponse.        recalcule souvent extrémités uniques. Les nombres impairs d'une fin donnée veiller à ce que l'on doit être abandonné (vous obtenez 2 billets de faveur aux extrémités). mots qui correspondent peut Séparer les auto, vous pouvez toujours les jeter dans la dernière, et ils muck le calcul autrement. Vous pouvez être en mesure de créer de petits anneaux correspondants auto, vous pouvez traiter ces mots comme auto correspondants, tant que vous ne les orphelins lorsque vous les créez. Cela peut rendre la performance fantastique, mais aucune garantie sur une solution parfaite.

L'espace de recherche est l'ordre (N!) Une liste de millions d'éléments peut être difficile de prouver une réponse exacte. Bien sûr, je pourrais être sur quelque chose.