Trouver des sous-séquences similaires connectées dans deux séquences données

Question

Je recherche des pointeurs vers des algorithmes qui trouveront longtemps connecté similaire Les sous-séquences dont deux séquences données ont en commun. Par exemple, en cas de deux chaînes:

abcaabbaabUVWXYZ
UVWXeYZababababab

Je m'intéresse à:

**********UVWXYZ
UVWXYeZ**********

Pas dedans:

ab*aabba*b*****
******aba*ab*bab

(ce qui serait un possible la plus longue subséquence commune pour les chaînes données).

Pour l'exemple ci-dessus, e représente une (petite) différence dans les chaînes autrement identiques UVWXYZ et UVWXeYZ. C'est là que le similarité entre. e n'est pas nécessairement un ajout d'un seul caractère. Cela peut également être un changement. Lorsque vous réfléchissez à des chaînes plus longues, plusieurs personnages (même en succession directe) peuvent être différents.

L'algorithme devrait probablement être motivé par un fonction de notation pour le longueur et le similarité des sous-séquences.

Je suis conscient que ce problème est plutôt vague, donc tous les pointeurs pour éventuellement les domaines de problème et les algorithmes correspondants sont également appréciés.

Mise à jour:Supprimé le critère d'exclusion "LCS", car cela semble être ce que je recherche.