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

Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 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 подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска.

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

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

Update: о текущем решение, я поддерживаю hash_map[M=20] где ключ это подстрока а значение это позиция где мы последний раз видели подстроку такой длины. В итоге на каждый запрос я проверяю есть ли такая подстрока длины 1, если есть то проверяю 2 и т.д. до 20, после чего возвращаю ответ из самой длинной совпадающей. Сложность M*M в худшем. Когда приходит новый char я обновляю hash_map[1][new_char]=cur_pos, если в hash_map уже была позиция для [new_char] то я пропагандирую ее на длину 2 и так пока не получу уникальное место, тут тоже примерно M операция, в худшем случае M*M. В итоге имею не оптимальный ответ но как минимум длины 20 если такой существует.