Calcul de la sous-chaîne commune la plus longue de deux chaînes à l'aide de tableaux de suffixes

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

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

J'ai essayé de l'implémenter, mais comme de nombreux détails d'implémentation n'ont pas été (c'est-à-dire lors de la concaténation des chaînes, dois-je mettre un caractère spécial entre elles ( )?), Mon code a échoué sur de nombreux cas de test. Quelqu'un pourrait-il élaborer davantage sur cet algorithme?$AcB$

Merci d'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 que cela fonctionne. Si vous pensez que c'est incorrect, veuillez suggérer un autre algorithme.

Votre algorithme est incorrect . Je suppose que vous savez comment calculer le tableau de suffixes et le tableau LCP d'une chaîne, c'est-à-dire leur mise en œuvre efficace. Comme cela a été souligné dans les commentaires, vous devez essayer de comprendre ce qu'est chaque composant et pourquoi il fonctionne.

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

Vient ensuite le tableau L C P [ i ] indique la longueur du préfixe commun le plus long entre les suffixes à partir de S A [ i - 1 ] et S A [ i ] . C'est-à-dire qu'il garde une trace de la longueur du préfixe commun le plus long parmi deux suffixes consécutifs de S lorsqu'ils sont disposés dans l'ordre lexicographique.$LCP$$LCP[i]$$SA[i-1]$$SA[i]$$S$

Par exemple, considérons la chaîne . Les suffixes dans l'ordre lexicographique seraient { a , a b b a b c a , a b c a , b a b c a , b b a b c a , b c a , c a } , donc S A = [ 7 , $S = abbabca$$\{a, abbabca, abca, babca, bbabca, bca, ca\}$ pour un tableau indexé 1. Letableau L C P serait L C P = [ - , 1 , 2 , 0 , 1 , 1 , 0 ] .$SA = [7, 1, 4, 3, 2, 5, 6]$$LCP$$LCP = [-, 1, 2, 0, 1, 1, 0]$

Maintenant, étant donné deux chaînes 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 du choix d'un tel caractère est que lors du calcul du LCP de deux suffixes, disons a b # d a b d et a b d , la comparaison s'arrête à la fin de la première chaîne (car elle ne se produit qu'une seule fois, deux suffixes différents ne l'auront jamais dans la même position) et ne "déborderont" pas dans l'autre chaîne.$A$$B$$S = A\#B$$\#$$A$$B$$ab\#dabd$$abd$

Maintenant, on peut voir que vous devriez pouvoir voir pourquoi vous n'avez besoin que de voir des valeurs consécutives dans le tableau (l'argument est basé sur la contradiction et le fait que les suffixes dans S A sont dans l'ordre lexicographique). Continuez à vérifier le tableau L C P pour la valeur maximale de sorte que les deux suffixes comparés n'appartiennent pas à la même chaîne d'origine. S'ils n'appartiennent pas à la même chaîne d'origine (l'un commence en A et l'autre en B ), la plus grande valeur est la longueur de la plus grande sous-chaîne commune.$LCP$$SA$$LCP$$A$$B$

Par exemple, considérons et B = b c . Alors, S = a b c a b c # b c . Les suffixes triés sont { a b c # b c , a b c a b c # b c , b c , b c # b c , b c $A = abcabc$$B = bc$$S = abcabc\#bc$ . S $\{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 , mais il est à S A [ 1 ] et S A [ 2 ] , les deux qui commencent dans la chaîne A . Donc, nous ignorons cela. En revanche, L C P [ 4 ] = 2 est pour S A [ 3 ] (correspond au suffixe b c de B ) et S A [ 4 $LCP[2] = 3$$SA[1]$$SA[2]$$A$$LCP[4] = 2$$SA[3]$$bc$$B$$SA[4]$(correspondant au suffixe de A ). Il s'agit donc de la sous-chaîne commune la plus longue entre les deux chaînes. Pour obtenir la sous - chaîne réelle, on prend une longueur 2 (valeur de la plus grande possible L C P ) à partir de la sous - chaîne soit S A [ 3 ] ou S A [ 4 ] , qui est b c .$bcabc\#bc$$A$$2$ $LCP$$SA[3]$$SA[4]$$bc$

L'algorithme que vous avez trouvé en ligne n'est pas entièrement correct. Comme mentionné par Paresh, il échouera dans l'exemple donné par lui.

Cependant, si vous vous assurez qu'en vérifiant le LCP, vous ne vérifiez que le LCP des sous-chaînes de chaînes différentes. Par exemple, si vous trouvez le LCS des chaînes A et B, vous devez vous assurer que les entrées adjacentes du tableau de suffixes lors de la vérification de LCP ne proviennent pas toutes les deux de la même chaîne.

Plus de détails ici .

Je pense que quelque chose comme l'algorithme que vous citez devrait en effet fonctionner si un caractère qui ne fait pas partie du jeu de caractères est utilisé comme séparateur, et les tableaux de suffixes / préfixes sont construits pour exclure toutes les chaînes qui contiennent le séparateur, probablement l'intention du designer. cela revient à construire des tableaux de suffixes / préfixes pour les deux chaînes distinctes.

il serait utile pour une future référence si vous publiez un lien vers l'algorithme. notez que wikipedia a l'algorithme pour cela dans le pseudocode et de nombreux autres algorithmes. et il existe des implémentations dans la plupart des langues standard disponibles en ligne.