Тема: Запрос на суффиксном автомате
Есть ли нормальный способ для поиска состояния суффиксного автомата, соответствующего подстроке строки, на котороый он был построен, заданной ее левым и правым индексами? Формально, есть суффиксный автомат, построенный на строке S. Поступают запросы вида "найти состояние в автомате, соответствующее подстроке S[l]...S[r]".
Вроде бы ясно, как это можно сделать в оффлайне за O((N + M)logN). Для этого достаточно предпосчитать двоичные прыжки по суффиксным ссылкам, отсортировать запросы по правому концу и для фиксированного правого конца за O(logN) находить следующее интересующее нас состояние.
Можно ли это делать в онлайне и быстрее? Даже если можно в оффлайне делать это быстрее и проще, тоже было бы интересно услышать.