удивления псто

[rgu]

Решаю задачки отсюда: http://rosalind.info/problems/tree-view/
Задача нахождения наибольшей общей подстроки многих строк (LCSM). Количество строк порядка сотни, длина каждой - порядка тысячи символов

Comments

[rgu]

К n-му шагу каждая пара хранит, где в каждой из строк находится макс. подстрока и какой она длины?
Ну так (n+1)-я строка может иметь общую подстроку, не имеющую ничего общего с предварительно вычисленным.
AAAAZBB
AAAYBB
AAAAAXBBB
к данному моменту мы запомнили AAA, а теперь видим такое:
BB

получается, что запоминать надо было другое. Или я неверно понял динамику?

[rgu]

а, я сразу не понял, что ВСЕ подстроки собираешься хранить
Да, я сделал bruteforce_решение, которое, как ни странно, сработало за разумное время даже на питоне.
Суффиксные деревья ненадолго откладываются...

[rgu]

Мне кажется, что мой пример показывает, что хранить только максимальные подстроки недостаточно -- при обработке новой строки может оказаться, что общей подстрокой теперь будет мЕньшая.

[rgu]

Да, я не понял вначале, что ты хранишь макс. общие подстроки, начинающиеся ВО ВСЕХ позициях. Думал почему-то, что только одну максимальную всех предыдущих.