Семинар 1. LCP, поиск палиндромов, ДКА

Вычисление всех LCP(suffix(A), suffix(B)) за O(M*N) простой динамикой.

Полиномиальное хеширование. Вычисление хеша от подстроки за O(1) с предподсчётом степеней основания. Предположение об идеальности хеша для всех встречающихся в задаче строк (обычно это все подстроки входных строк). Определение равенства подстрок за O(1). Вычисление LCP вида LCP(suffix(A), suffix(B)) за O(log N) бинарным поиском. Проблема разрешения коллизий.

Поиск подстрок-палиндромов. Тривиальное решение за O(N^3). Простое решение за O(N^2). Размер ответа O(N^2). Идея: возвращаем ответ в сжатом виде. Четный(*) и нечётный случаи. Сжатый вид: для каждого i ищем Q(i) - длину макс. палиндрома с центром в i. Вычисление Q слева направо. Использование блока. Хранение блока с макс. правой границей. (Алгоритм аналогичен алгоритму поиска Z-функции).

Детерминированный конечный автомат (ДКА). Смысл, картинка, определение. Конфигурации и такты. Распознаваемый язык L(A). Слив. Примеры: натуральные числа; кратные D; палиндромы (неуспешно).