1

Тема: Наибольшая общая подпоследовательность(быстрый алгоритм)

Найти наибольшую общую подпоследовательность двух строк - известная задача, и хорошо известно, как её решать за O(n*m). Однако, на википедии сказано, что существуют и другие, более быстрые алгоритмы. Хотелось бы узнать, какие они бывают.

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

2

Re: Наибольшая общая подпоследовательность(быстрый алгоритм)

Большинство таких алгоритмов предназначены для особых случаев, и в общем случае (на произвольных строках и с большим алфавитом) работают не сильно лучше наивного алгоритма за O(n^2).

В статье, на которую ссылается Википедия ("A Survey of Longest Common Subsequence Algorithms" - Bergroth, Hakonen, Raita, 2000), написано:

Of the current methods, the O(n^2/ log n) algorithm of Masek and Paterson [28] is theoretically the fastest known.

В общем, как мне кажется, с точки зрения олимпиад изучение таких алгоритмов никакого профита не даст (хотя в каких-то отдельных ограниченных случаях - например, когда известно, что LCS имеет небольшую длину, - эти алгоритмы могут работать гораздо быстрее).