Je recherche un algorithme efficace pour faire carrelage de chaîne . Fondamentalement, vous recevez une liste de chaînes, disons Actuellement, j'utilise un algorithme légèrement naïve, qui fonctionne comme suit. En commençant par une paire de chaînes aléatoires, disons Bien que cela fonctionne, ce n'est pas très efficace, car il itière sur les mêmes personnages encore et encore. Alors, quelqu'un connaît-il un algorithme Merci d'avance. << pour les situations Là où il y a une ambiguïté - par exemple, Question similaire: BCD , CDE , abc , a et la chaîne tiled résultat doit être abcde ABCDE , parce que bcd aligne avec CDE céder BCDE , qui est ensuite aligné avec abc donnant la finale abcde . BCD et CDE , j'utilise ce qui suit (en java): {abc, cba} qui pourrait entraîner un abcba ou cbabc -, tout carrelage peut être renvoyé. Cependant, cette situation se produit rarement, car je vous enlève des mots, par exemple. {Ceci est, c'est moi} => {ceci est moi} , qui sont manipulés de sorte que l'algorithme susmentionné fonctionne.
5 Réponses :
La première chose à poser est si vous voulez trouver le labour de {CDB, CDA}? Il n'y a pas de labourage unique.
Non, j'ai besoin d'un chevauchement complet de l'une des cordes. En utilisant mon algorithme, cette paire de chaînes retournerait la chaîne vide.
Un algorithme approximatif simple serait de construire un graphique de De Bruijn. Je pense aux autres.
@Lasse V. Karlsen: C'est un cas intéressant, car il existe deux combinaisons possibles ("ABC" + "CDE" ou "ABC" + "CFG"). Mais envisagez un seul carrelage de cordes paires.
Quelle est la sortie de cette paire {abc, cba}? Également vide en raison de l'ambiguïté? Qu'en est-il de cette {ABC, BCA}? Préfère Abca parce que le chevauchement est plus long? Permettez-vous des allumettes imparfaites? Il est difficile d'aller plus loin sans une image complète de votre problème.
@ LH3: "Abcba" et "Abca", respectivement. Fondamentalement, je vais d'abord essayer de teinter de la "droite" puis à la "gauche". Je n'ai pas tenu compte de ces cas, parce que je suis en train de mentionner des mots (par exemple "le roi" et "roi" => "Le roi est"), mais j'ai simplifié mes exemples parce que je pensais que ce serait plus facile d'expliquer . Qu'entendez-vous par les matchs imparfaites? Merci pour l'intérêt, BTW.
@JG: Si vous pensez principalement à deux chaînes, vous pouvez construire un arbre suffixe pour la première chaîne et numériser à travers la deuxième chaîne contre le suffixe. La complexité de temps est O (L) où L est la longueur totale des deux cordes.
@JG: Je me rends compte que vous pouvez également utiliser KMP, ce qui est plus facile à mettre en œuvre. La complexité de temps devrait également être linéaire.
@ LH3: J'ai examiné KMP, et cela améliorerait effectivement la période d'exécution de l'algorithme, en supprimant la sous-chaîne répétée appel. Maintenant, concernant le graphique Brujin, soin d'expliquer comment l'utiliser dans cette situation?
Je pense que cela devrait fonctionner pour le carrelage de deux chaînes et être plus efficace que votre mise en œuvre actuelle à l'aide de la sous-chaîne et contient. Conceptuellement, je bouffonne sur les caractères de la chaîne "gauche" et comparez-les à un caractère de la chaîne "droite". Si les deux caractères correspondent, je passe au caractère suivant de la chaîne de droite. En fonction de la chaîne de la fin, la fin est atteinte, et si les derniers caractères comparés correspondent ou non, l'un des cas de carrelage possibles est identifié.
Je n'ai pensé à rien d'améliorer la complexité de la carrelage plus de deux cordes. Comme une petite note pour plusieurs chaînes, cet algorithme ci-dessous est facilement étendu à la vérification du carrelage d'une seule chaîne «gauche» avec plusieurs chaînes «droites» à la fois, ce qui pourrait éviter une boucle supplémentaire sur les cordes si vous essayez de Découvrez s'il faut ["ABC", "BCX", "XYZ") ou ("ABC", "XYZ", BCX ") en essayant simplement toutes les possibilités. P>
string Tile(string a, string b)
{
// Try both orderings of a and b,
// since TileLeftToRight is not commutative.
string ab = TileLeftToRight(a, b);
if (ab != "")
return ab;
return TileLeftToRight(b, a);
// Alternatively you could return whichever
// of the two results is longest, for cases
// like ("ABC" "BCABC").
}
string TileLeftToRight(string left, string right)
{
int i = 0;
int j = 0;
while (true)
{
if (left[i] != right[j])
{
i++;
if (i >= left.Length)
return "";
}
else
{
i++;
j++;
if (i >= left.Length)
return left + right.Substring(j);
if (j >= right.Length)
return left;
}
}
}
Commandez les chaînes par le premier caractère, puis la longueur (la plus petite au plus grande), puis appliquez l'adaptation à KMP trouvée dans cette question sur la concaténation des chaînes superposées.
Merci, je cherchais un carrelage et un alignement et je n'ai pas trouvé cette question.
Il était difficile le trouver. Heureusement, j'avais répondu cela, donc il s'est réduit un peu la recherche.
problème intéressant. Vous avez besoin d'une sorte de backtracking. Par exemple, si vous avez:
ABCDBC.
Oui, je dois approfondir cela. L'alternative consiste à générer tous les permutations N! des chaînes, puis passez de gauche à droite pour chaque permutation possible, mais c'est évidemment uber-lent.
Si le code source ouvert est acceptable, vous devriez vérifier les points de repère
+1 pour une question bien écrite (mais vraiment pour trouver le
ï clé 8-)La touche ï au système d'exploitation X est
alt + u pour obtenir le UMLaut suivi dui auquel il est appliqué.Très proche de Stackoverflow.com/ Questions / 1285434 / ... .