1

Тема: Запрос на суффиксном автомате

Есть ли нормальный способ для поиска состояния суффиксного автомата, соответствующего подстроке строки, на котороый он был построен, заданной ее левым и правым индексами? Формально, есть суффиксный автомат, построенный на строке S. Поступают запросы вида "найти состояние в автомате, соответствующее подстроке S[l]...S[r]".

Вроде бы ясно, как это можно сделать в оффлайне за O((N + M)logN). Для этого достаточно предпосчитать двоичные прыжки по суффиксным ссылкам, отсортировать запросы по правому концу и для фиксированного правого конца за O(logN) находить следующее интересующее нас состояние.

Можно ли это делать в онлайне и быстрее? Даже если можно в оффлайне делать это быстрее и проще, тоже было бы интересно услышать.

2

Re: Запрос на суффиксном автомате

А зачем оффлайн, почему нельзя запомнить состояние автомата для каждого правого конца R?

Про способы без двоичного подъема не слышал.

3

Re: Запрос на суффиксном автомате

Да, действительно, можно и в онлайне с двоичными прыжками. Я думал, может как-то при построении можно только для нужных нам подстрок запоминать состояния, чтобы в сумме за линию было.

4

Re: Запрос на суффиксном автомате

В пользу того, что линейного решения нет, говорит такое соображение. Суфф.автомат примерно эквивалентен суфф.дереву, но на суфф.дереве большинство задач осознавать проще. В суфф.дереве задача поиска вершины, соответствующей подстроке [l;r], превращается в поиск такой вершины дерева, которая отстоит на нужном расстоянии от некоторого листа. И эту задачу не видно как решать за линейное время даже в оффлайне.