Только что я сидел разбирался с суффиксным автоматом (вроде бы все понятно и пишу норм, но если долго не писать забывается) и в примере задач увидел задачу из заголовка.
Ссылка на статью на e-maxx'e, там в примере задач она последняя.
Ну в общем убил я где-то минут 30-40 на то чтоб понять это, но толку нет. Не все так просто как казалось. Увы...
Но буквально пару минут я вспомнил о боре, и подумал: "а чего я хочу этого именно от суффиксного автомата, если это можно сделать в разы проще бором?"
Моя идея в том чтобы просто забросить все строчки в бор, а потом обходом в глубину (хотя зачем?) просто переходить по состояниям пока есть переход только по одной букве, иначе понятно, что уже общего префикса не будет. Идея проще простого, да и написать это очень легко.
Вот код.
Upd. Как же я люблю тупить... На e-maxx'e описано решение задачи о нахождении наибольшей общей подстроки. А префикс можно искать намного проще даже втупую, хотя втупую придется каждый раз пробегать за количество строк, чтобы сравнить равны ли соответствующие символы. Но все же этот алгоритм вполне можно использовать.
Извиняюсь за тупку, не судите строго.
Upd2. Да и идея наверное далеко не новая.
===========================================
И пользуясь моментом пару вопросов о автомате:
-Где можно было бы почитать о наибольшей общей подстроке нескольких строк, чтобы точно понять это?
-И раз уж пошел разговор о автомате, то можно ли, и как, сделать его персистентным? Т.е. добавлять символы очень удобно, но хотелось бы и уметь удалять их, хотя бы для начала по одному.
===========================================
Ура, я таки нашел в чем польза от этого способа. Немного изменив код, я пришел к онлайновости этого алгоритма. Каждый раз у меня будет хранится наибольший общий префикс для строк, которые у меня есть, а при добавлении новой, все пересчитывается во время добавления ее в бор. Код.
Если это такой же бесполезный алгоритм, скажите мне, как можно достичь такого же эффекта с онлайностью проще?