Видео: доклад Тани Стариковской (23.11.2012)

В эту пятницу состоялся доклад Тани Стариковской, на котором рассказывался алгоритм M. Crochemore и W. Rytter поиска наибольшей общей подпоследовательности (longest common subsequence) двух строк. LCS является классической задачей в области строковых алгоритмов и может быть решена за время с помощью динамического программирования (здесь и — это длины обеих строк).

Алгоритм авторов M. Crochemore и W. Rytter позволяет решить задачу за время , где — это длина машинного слова. На данный момент это один из наиболее практичных способов искать LCS. Все подробности на видео.