Автодополнение

Добавим все слова из словаря в бор. В боре помимо обычных переходов go будем также хранить обратные переходы по буквам back (означающие удаление буквы) и не более трех переходов, описывающих автодополнение — каждая вершина слова w имеет переход в вершину, обозначающую конец w. Так как популярность слова соответствует его индексу в словаре, хранить достаточно только первых три перехода, а остальные игнорировать.

После этого также добавим в бор требуемое сообщение s, однако уже без переходов-автодополнений. Пометим все вершины этого слова s как «хорошие» — при дописывании буквы в конец слова, оказаться мы можем только в них.

Осталось посчитать динамику на построенном боре. Пусть dp[k][v] — количество способов оказаться в вершине бора под номером v, сделав при этом ровно k ходов. Тогда из этого состояния мы можем перейти в состояния dp[k + 1][back[v][c]] (удаление буквы), dp[k + 1][go[v][c]] (дописывание буквы, надо также не забыть проверить, что go[v][c] — «хорошая» вершина и dp[k + 1][autocompletion[v][index]] (соглашение с автодополнением) для некоторых букв c (если такие состояние существуют, то есть существуют такие вершины в боре).

Ответом на задачу будет , где finish — номер вершины бора, соответствующей концу слова s. Асимптотика решения — .