J'essaie de trouver un moyen de trouver la plus grande sous-chaîne dupliquée dans un groupe de chaînes. Le longest duplicate substring problem s'applique généralement à une seule chaîne au lieu d'un groupe de chaînes. Quel type d'algorithme serait utile pour trouver la plus grande sous-chaîne dupliquée dans un groupe de chaînes? Trouver la plus grande chaîne dupliquée dans un groupe de fichiers (afin de supprimer le code dupliqué dans les grandes bibliothèques logicielles) est le cas d'utilisation principal que j'ai à l'esprit, mais il y aurait beaucoup d'autres cas d'utilisation pour cet algorithme. .Trouver la plus longue sous-chaîne répétée dans un groupe de chaînes
Par exemple, je veux trouver la plus longue chaîne en double dans ce groupe de chaînes:
"Hello world, this is the first string."
"Hello to the world, this is the second string."
"Hello world. This is the third string."
"This is the third string."
Dans ce cas, "This is the third string." serait la plus longue chaîne répétée (ie, la plus longue chaîne qui apparaît dans plus d'une de ces chaînes).
Une approche possible serait pour générer un séparateur pour chacune des chaînes, et concaténer chaque chaîne dans une chaîne, avec le séparateur étant entre chaque chaîne. Le séparateur doit être une chaîne qui n'a été trouvée dans aucune des chaînes existantes. Ensuite, je pourrais utiliser le même algorithme qui est utilisé pour trouver la plus longue sous-chaîne en double pour une seule chaîne. –
@Andy Pourquoi, bonjour là! S'amuser en SMC, sommes-nous? ;) Quoi qu'il en soit, je suis assez sûr que si vous concaténer les chaînes et ensuite appliquer l'algorithme d'origine, vous pouvez avoir plus de chance. –
Bien que vous souhaitiez d'abord marquer votre entrée, ne pas chercher caractère par caractère. En fonction de la manière dont vous l'implémentez, cela pourrait accélérer la mise en œuvre globale. –