Тема: Наибольшая общая подпоследовательность(быстрый алгоритм)
Найти наибольшую общую подпоследовательность двух строк - известная задача, и хорошо известно, как её решать за O(n*m). Однако, на википедии сказано, что существуют и другие, более быстрые алгоритмы. Хотелось бы узнать, какие они бывают.
Например есть такой алгоритм: заменить каждую букву строки B на упорядоченный по убыванию список вхождений этой буквы в строку A, а потом найти в этом списке наибольшую возрастающую подпоследовательность. К сожалению, этот алгоритм работает на двух строках вида aa...a длины n за время O(n^2 log n).