K
как решить ее с суфф массом ?
а зачем не дерево мапов?
Size: a a a
2020 March 26
Ш
Я не слышал о таком
Ш
а зачем не дерево мапов?
Это случайно не бор?)
K
ага, он
K
думаете, я помню, как оно называеться
Ш
А как эту задачу бором можно решить
K
А как эту задачу бором можно решить
подожди минут 20, напишу
DK
что тут писать
DK
Вставляем в бор все команды, теперь каждой команде соответствует какой-то лист (по условию)
DK
Рассмотрим все листы, поднимаемся по ним вверх, вызывая pop_back у соответствующей строки. Если у предка больше двух поддеревьев, то заканчиваем подьем и выводим ответ, иначе удаляем последний символ и переходим к рассмотрению предка текущего листа
K
ну, я бы писал за n*l*l (10^7, в тл влезет
DK
Можно неявный бор использовать
DK
Посортируем все строки, дополним до одинаковой длины символами $
DK
Теперь делаем бинпоиск по посорченному вектору для каждого префикса
DK
O(N * L * log(N))
K
Теперь делаем бинпоиск по посорченному вектору для каждого префикса
простите, а если минимальная подстрока - не префикс?
DK
не может быть не префиксом
DK
ААА
K
первый тест