Вчера закончился длинный тур Открытой олимпиады 2024-25, мне оттуда очень понравилась задача F (инопланетные омофоны). Возможно, некоторые скажут, что там очевидное решение (про которое я тоже напишу), но я таких идей раньше не встречал и не думал в ту сторону. Зато я придумал другое решение, более техничное, но тоже интересное.

Само условие можно найти тут.

Общие идеи для решения:

Чтение очередного слога я буду называть прыжком по строке. Прыжок зависит от текущий позиции (его старт) и от правой границы, до которой мы прыгаем. Слово, которое мы получаем, по факту является массивом из типов звуков. Сравнение двух слов — это сравнение этих двух массивов на равенство. Делать это не хешами звучит очень сложно, поэтому для сравнения подотрезков нам нужно будет посчитать их хеши. Также, для определения, какой именно звук мы произнесём при прочтении слога, мы по факту должны выделить компоненты связности, слоги из одной компоненты звучат одинаково, а из разных — по-разному. Ну и наконец, для определения прыжка очень полезен будет алгоритм Ахо-Корасик, без него никуда не деться. Так как при прыжке у нас фиксирован старт, а конец не фиксирован, строки из набора следует развернуть, а затем проходиться по строке справа-налево (обычный Ахо-Корасик умеет находить слова, которые заканчиваются в какой-то позиции, а если мы разверём слова и направление прохода, то получим слова, которые начинаются в какой-то позиции).

Теперь же перейдём к решениям задачи. Нормальное решение, которое сдало (скорее всего) большинство сдавших, звучит так:

Мы умеем для позиции искать самое длинное слово, которое начинается в ней. Почему мы не можем всегда делать просто максимальные прыжки? В какой-то момент максимальный прыжок будет пересекать правую границу отрезка. Но до этого момента мы прыгать спокойно можем. А в момент пересечения возникает очень хитрое замечание: оставшийся отрезок строки, который надо пропрыгать — это префикс какой-то строки из набора. Так как суммарная длина строк в наборе $$$S \le 10^6 + 26$$$\, мы можем просто решить задачу для каждого префикса каждой строки, тогда мы победим. Информация, которая нам будет нужна — это хеш и количество прыжков, которые мы сделаем (нужны оба параметра для того, чтобы хеши прыжков с двух частей можно было объединить).

А чтобы решить задачу для префикса каждой строки, сделаем так: будем считать ответ в порядке возрастания длин строк в наборе. Тогда применима такая же идея — сначала мы прыгаем, сколько можем, а последний прыжок может оказаться префиксом какой-то строки, но мы её уже были обязаны рассмотреть. Таким образом, за $$$O(S)$$$ мы решили задачу для всех префиксов.

Чтобы быстро понимать в строке $$$t$$$, до куда мы допрыгаем по максимальным прыжкам, можно насчитать бинарные подъёмы. Итого получается $$$O(n \ log \ n)$$$ на эту часть. Общая сложность решения $$$O(n \ log \ n + S)$$$ (алфавит считаем константной).