Квантовое запутывание происходит, когда две частицы связываются определенным образом независимо от того, насколько далеко они находятся друг от друга в пространстве.
Дана строка \(s\). Две непустые подстроки \((a, b)\) называются запутанными, если существует (возможно, пустая) связующая строка \(c\) такая, что:
- Каждое вхождение \(a\) в \(s\) непосредственно следует за вхождением \(cb\);
- Каждое вхождение \(b\) в \(s\) непосредственно предшествует вхождению \(ac\).
Иными словами, \(a\) и \(b\) встречаются в \(s\) только как подстроки \(acb\). Вычислите общее количество запутанных пар подстрок строки \(s\).
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Выходные данные
Выведите одно целое число, количество запутанных пар подстрок строки \(s\).
Примечание
В первом примере единственная запутанная пара — (ab,ba). Для этой пары соответствующая связующая строка \(c\) пуста, так как они встречаются только как подстроки всей строки abba, которая не имеет никаких символов между ab и ba.
Во втором примере запутанных пар нет.
В третьем примере запутанные пары: (a,b), (b,c), (a,c), (a,bc) и (ab,c). Для большинства пар соответствующая связующая строка \(c\) пуста, за исключением пары (a,c), для которой связующая строка \(c\) равна b, так как a и c встречаются только как подстроки строки abc.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abba
|
1
|
|
2
|
abacaba
|
0
|
|
3
|
abcabcabcabc
|
5
|
|
4
|
adamant
|
82
|