Полулокальное сравнение строк

Вычисление наибольшей общей подпоследовательности (longest common subsequence, LCS) двух строк - одна из классических алгоритмических задач. Во многих приложениях необходимо обобщение этой задачи, которое мы называем полулокальной LCS (semi-local LCS). В этом случае требуется вычислить LCS между строкой и всеми подстроками другой строки, и/или между всеми префиксами одной строки и всеми суффиксами другой. Помимо важной роли этой обобщенной задачи в строковых алгоритмах, у нее открываются неожиданные связи с алгеброй полугрупп и вычислительной геометрией, с сетями сравнений (comparison networks), а также практические приложения в вычислительной биологии.

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