Пароли

Заметим, что условие задачи можно переформулировать следующим образом. Посчитайте количество способов разбить $$$s$$$ на три строки $$$a$$$, $$$b$$$ и $$$c$$$, так что $$$a \neq b$$$, $$$b \neq c$$$ и $$$a + b \neq b + c$$$.

Количество способов разбить $$$s$$$ на три отрезка — $$$C_{|s| - 1}^{2}$$$.

Вычтем количество способов, в которых $$$a = b$$$ или $$$b = c$$$. Чтобы посчитать количество разбиений, в которых $$$a = b$$$, переберем четную длину $$$l \cdot 2$$$ строки $$$a + b$$$, и проверим, что $$$s[1 \dots l] = s[l + 1 \dots l \cdot 2]$$$ (для этого можно, например, использовать z-функцию). Количество разбиений, в которых $$$b = c$$$, считается аналогично. Обратите внимание, что возможен случай, когда $$$a = b = c$$$. Его нужно учесть, и в таком случае, прибать $$$1$$$ к ответу.

Осталось вычесть количество разбиений, в которых $$$a \neq b$$$, $$$b \neq c$$$ и $$$a + b = b + c$$$. Для этого, переберем длину $$$l$$$ строки $$$a + b$$$. Проверим, что $$$s[1 \dots l] = s[|s| - l + 1 \dots |s|]$$$, $$$s[1 \dots |s| - l] \neq s[|s| - l + 1 \dots l]$$$ и $$$s[|s| - l + 1 \dots l] \neq s[l + 1 \dots |s|]$$$. Для этого тоже можно использовать z-функцию.