Plus longue sous-chaîne commune

Arbre des suffixes généralisé construit à partir des chaînes « ABAB », « BABA » et « ABBA », numérotées respectivement 0, 1 et 2.

La plus longue chaîne commune à un ensemble de chaînes peut être déterminée en construisant l'arbre des suffixes généralisé puis en trouvant le nœud le plus profond ayant des feuilles pointant vers toutes les chaînes. Dans l'exemple ci-contre, le nœud auquel on arrive par « AB » a quatre feuilles dans son sous-arbre ; la feuille de gauche dit qu'une occurrence de la sous-chaîne « AB » commence en position 2 dans la chaîne 0 (« ABAB »), de même, la feuille de droite indique une occurrence débutant en position 0 dans la chaîne 2 (« ABBA ») ; des deux feuilles centrales, celle de gauche indique qu'une occurrence de la sous-chaîne « ABA » commence en position 1 dans la chaîne 1 (« BABA »).

La construction de l'arbre des suffixes a une complexité en temps de ${\displaystyle \Theta (N)}$, où ${\displaystyle N}$ est la somme des longueur des chaînes représentées.

La recherche peut se faire en temps similaire grâce à des algorithmes de plus petit ancêtre commun[1].

Dans un premier temps, on cherche le plus long suffixe commun pour chaque paire de préfixes des deux chaînes ${\displaystyle S}$ et ${\displaystyle T}$. Le plus long suffixe commun du préfixe ${\displaystyle S[1,p]}$ de longueur ${\displaystyle p}$ de ${\displaystyle S}$ et du préfixe ${\displaystyle T[1,q]}$ de longueur ${\displaystyle q}$ de ${\displaystyle T}$ est

${\displaystyle {\mathsf {PLSuff}}(S[1,p],T[1,q])={\begin{cases}{\mathsf {PLSuff}}(S[1,p-1],T[1,q-1])+1&{\text{si }}S[p]=T[q]\\0&{\text{sinon}}.\end{cases}}}$

Pour les chaînes « ABAB » et « BABA », on obtient:

		A	B	A	B
	0	0	0	0	0
B	0	0	1	0	1
A	0	1	0	2	0
B	0	0	2	0	3
A	0	1	0	3	0

Le plus grand de ces suffixes communs à tous les préfixes est la plus longue sous-chaîne commune. Dans la table, elles sont indiquées en rouge, et dans l'exemple, les deux sous-chaînes communes de longueur maximale sont « ABA » et « BAB ».

${\displaystyle {\mathsf {PLSC}}(S,T)=\max _{1\leq p\leq m \atop 1\leq q\leq n}{\mathsf {PLSuff}}(S[1,p],T[1,q]).}$

La méthode peut être étendue à plus de deux chaînes en ajoutant des dimensions à la table.