Le calcul de la plus longue chaîne commune de deux chaînes en utilisant des tableaux de suffixe

Question

Après avoir appris comment construire un tableau de suffixe en $ O (N) $ complexité, je suis intéressé à découvrir les applications des tableaux de suffixe. L'un d'eux est de trouver la plus longue entre deux sous-chaîne commune cordes, en $ O (N) $ temps. J'ai trouvé sur Internet l'algorithme suivant:

1. fusionner les deux chaînes $ A $ et $ B $ en une seule chaîne $ AB $
2. calculer le tableau de suffixe de $ AB $
3. calculer le tableau $ LCP $ (le plus long préfixe commun)
4. la réponse est la plus grande valeur LCP $ [i] $

J'ai essayé de le mettre en œuvre, mais autant de détails de mise en œuvre ne sont pas dit (i.e.. Quand concaténer les cordes, dois-je mettre un caractère spécial entre eux ($ AcB $)?), Mon code a échoué sur de nombreux cas de test. Quelqu'un pourrait-il expliquer davantage cet algorithme?

Merci à l'avance.

Remarque: Je ne garantis pas l'exactitude de cet algorithme; Je l'ai trouvé sur un blog, et je ne suis pas sûr qu'il fonctionne. Si vous pensez qu'il est incorrect, s'il vous plaît suggérer un autre algorithme.

Answer 1

Votre algorithme est incorrect . Je suppose que vous savez comment calculer le tableau de suffixe et la matrice de LCP d'une chaîne, qui est, leur mise en œuvre efficace. Comme il a été souligné dans les commentaires, vous devriez essayer de comprendre ce que chaque composant est, et pourquoi il fonctionne.

Tout d'abord, est le tableau de suffixe ($ SA $) d'une chaîne. Un tableau de suffixe est essentiellement tous les suffixes de la chaîne $ S $ disposés en ordre croissant lexicographique. Plus précisément, la valeur $ SA [i] $ indique que le suffixe de $ S $ à partir de la position $ SA [i] $ est classé $ i $ dans l'ordre lexicographique de tous les suffixes de $ S $.

Ensuite est la matrice LCP $ de $. $ LCP [i] $ indique la longueur de la plus longue commune préfixe entre les balises suffixes à partir de $ SA [i-1] $ et $ SA [i] $. Autrement dit, il garde la trace de la longueur du plus long préfixe commun entre les deux suffixes consécutifs de $ S $ lorsqu'ils sont disposés dans l'ordre lexicographique.

À titre d'exemple, considérez la chaîne $ S = abbabca $. Les suffixes dans l'ordre lexicographique seraient $ \ {a, abbabca, ABCA, babca, bbabca, bca, ca \} $, donc $ SA = [7, 1, 4, 3, 2, 5, 6] $ pour 1 tableau -indexed. La matrice LCP $ $ serait de $ LCP = [-, 1, 2, 0, 1, 1, 0]. $

Maintenant, étant donné deux chaînes $ A $ et $ B $, nous les concaténer comme $ S = A \ # B $, où $ \ # $ est un caractère non présent à la fois $ A $ et $ B $. La raison de choisir un tel caractère est ainsi que lors du calcul du LCP de deux suffixes, disons $ ab \ # DABD $ et $ abd $, la comparaison se répartiront à la fin de la première chaîne (car il se produit une seule fois, deux suffixes différents auront jamais dans la même position), et ne sera pas « débordement » dans l'autre chaîne.

Maintenant, on peut voir que vous devriez être en mesure de voir pourquoi vous ne devez voir les valeurs consécutives dans le tableau de LCP $ de $ (l'argument est fondé sur la contradiction et le fait que les suffixes de $ SA $ sont en lexicographique ordre). Continuez à vérifier le tableau de LCP $ M $ pour la valeur maximale tels que les deux étant comparés ne suffixes pas appartenir à la même chaîne d'origine. Si elles ne le font pas appartenir à la même chaîne d'origine (on commence en $ A $ et l'autre en $ B $), alors la plus grande valeur telle est la longueur de la plus grande sous-chaîne commune.

À titre d'exemple, pensez à $ A = abcabc $ et $ B = bc $. Ensuite, $ S = abcabc \ # bc $. $ sont triés suffixes \ {abc \ #BC, abcabc \ #BC, bc, bc \ #BC, bcabc \ #BC, c, c \ #BC, CABC \ #BC \} $.
$ \ Begin {align *} SA & = [4, 1, 8, 5, 2, 9, 6, 3, 7] \\ LCP & = [-, 3, 0, 2, 2, 0, 1, 1, 0] \ End {align *} $

Maintenant, la plus grande valeur est de $ LCP [2] = 3 $, mais il est pour $ SA [1] $ et $ SA [2] $, les deux qui commencent dans la chaîne $ A $. Donc, nous ignorons cela. D'autre part, $ LCP [4] = $ 2 $ est pour SA [3] $ (correspond au suffixe $ $ bc de $ B $) et $ SA [4] $ (correspondant au suffixe bcabc $ \ #BC $ de $ A $). Donc, c'est la plus longue chaîne commune entre les deux chaînes. Pour obtenir la sous-chaîne réelle, vous prenez une longueur de 2 $ (valeur du plus grand possible $ $ LCP) substring à partir soit $ SA [3] $ ou $ SA [4] $, ce qui est $ bc $.

Answer 2

L'algorithme que vous avez trouvé est en ligne pas tout à fait correct. Comme mentionné par Paresh, il échouera dans l'exemple donné par lui.

Cependant, si vous vous assurez que lors de la vérification du LCP, vous vérifiez que le LCP de sous-chaînes de chaînes différentes. Par exemple, si vous trouvez le LCS de chaînes A et B, alors vous devez vous assurer que les entrées adjacentes du tableau Suffixe lors de la vérification pour LCP sont tous les deux pas de la même chaîne.

Plus de détails ici .

Answer 3

Je pense que quelque chose comme l'algorithme vous citez devrait en effet le travail si un personnage qui ne fait pas partie du jeu de caractères est utilisé comme séparateur, et le suffixe / préfixe des tableaux sont construits pour exclure toutes les chaînes qui contiennent le séparateur, sans doute l'intention du concepteur. cela est essentiellement équivalent à la construction de tableaux suffixe / préfixe pour les deux chaînes distinctes.

il serait utile pour l'avenir ref si vous posté un lien vers l'algorithme. noter que wikipedia a l'algorithme pour cela dans beaucoup d'autres et pseudocode algorithmes. et il y a des mises en œuvre dans la plupart des langues standard disponibles en ligne.