Здравствуйте, столкнулся с такой задачей:

Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 1 запрос на 10 символов): найти max длину подстроки между (pointer, cur_pos) которая повторяет строку начинающуюся с (pointer).

Например, для строки (abcab[запрос префикса с 0, ответ длина 2, pos 3]cab[запрос префикса с 2, ответ длина 3, pos 5]). Т.е. для первого запроса ищем префикс abcab на участке bcab, находим ab; Для второго запроса ищем префикс cabcab на участке abcab, находим cab.

Сейчас решаю ее с помощью хешей, но не устраивает производительность, на больших данных слишком много cache misses.

Знает ли кто-то возможно ли решение быстрее? В теории суффиксное дерево позволяет искать max подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска.

Хочется алгоритм с маленьким средним временем работы и маленьким расходом памяти, в целом, устроят примерные решения, когда находится не самый длинный префикс но близкий к нему.

Если кто-то может дать направление куда копать с такой задачей то буду очень признателен,