В моих экспериментах (несколько лет назад) никогда не получалось заставить работать подобную структуру быстрее аккуратно написанного "китайского дерева отрезков" (https://codeforces.com/blog/entry/18051), более того, есть версии ДО, которые ещё сильнее оптимизированы с помощью SIMD инструкций (https://codeforces.com/blog/entry/89399).
Шаг 5 можно делать за линейное время, например, с помощью суффиксного автомата (возможно, есть и более простые способы это сделать).
Упрощённый пример (для каждого суффикса исходной строки найти наибольший префикс, который полностью встречается раньше суффикса): https://godbolt.org/z/eeM4sccdM
В моих экспериментах (несколько лет назад) никогда не получалось заставить работать подобную структуру быстрее аккуратно написанного "китайского дерева отрезков" (https://codeforces.com/blog/entry/18051), более того, есть версии ДО, которые ещё сильнее оптимизированы с помощью SIMD инструкций (https://codeforces.com/blog/entry/89399).
Да, тут тоже будет проблема с памятью. В частности, текущая версия использует 1024*вес строки памяти, но можно дооптимизировать константу до ~10.
И конечно, без данных нельзя предсказать будет ли вообще моё решение работать быстрее вашего)
Шаг 5 можно делать за линейное время, например, с помощью суффиксного автомата (возможно, есть и более простые способы это сделать).
Упрощённый пример (для каждого суффикса исходной строки найти наибольший префикс, который полностью встречается раньше суффикса): https://godbolt.org/z/eeM4sccdM