Наибольшая общая подпоследовательность (LCS)

Для упрощения длины обоих строк одинаковые.

* Алгоритм Нудельмана-Вунша – O(n*n)

* Реализация LCS на основе LIS(Наибольшая возрастающая подпоследовательность) – O(n*n*log(h), в среднем O(n*log(h))

* Алгоритм Эллисона-Дикса – O(n*n/32) 

обозначения:
n – длина строки,
h – количество общих буквенных пар. Т.е. если в первой строке есть 3, а во второй - 2 буквы ‘a’, то количество общих буквенных пар для ‘a’ равно 6.