1

Тема: Суффиксный автомат. Наибольшая общая подстрока нескольких строк.

Предлагаю алгоритм, немного лучший, чем описанный здесь: http://e-maxx.ru/algo/suffix_automata#27.
Будем решать задачу как для двух строк, то есть построим автомат для первой строки S[0], будем бежать по префиксам второй S[k] и находить максимальный суффикс этого префикса, входящий в S[0]. Всё, как в соостветсвующей статье, но при этом будем запоминать, например в массив nowlen[], что для состояния V мы нашли длину Len. После обработки строки, нужно вспомнить, что у состояний есть суффиксные ссылки, а значит эти длины нужно "просеить" вверх по этим ссылкам. Если L = link[V], то nowlen[L] = min(len[L], nowlen[V]). Чтобы это сделать за O(n) можно отсортировать состояния по длине какой-нибудь линейной сортировкой (списочной или поразрядной), и пробежаться от большего к меньшему. Теперь пусть у нас есть для предыдущих k-1 строк ответ на задачу, но в неявном виде: ans[V] - это максимальная длина состояния V, что оно входит в первые k-1 строк. В явном виде ответ - это максимум на этом массиве. Осталось самое простое - объединить результаты ans и nowlen, очевидно, что ans[V] = min(ans[V], nowlen[V]). Изначально ans равен длинам сотояний в S[0].
У алгоритма получилась такая же ассимптотика, но он гораздо выгоднее по памяти. Во-первых нет разделителей, а значит меньше алфавит, во вторых автомат нужно строить только для одной строки, лучше для самой короткой.

P.S. можно добавить задачу "1227 - The longest constant gene" с uva

2

Re: Суффиксный автомат. Наибольшая общая подстрока нескольких строк.

Под автоматом все такие, смелые