La pareidolia es el fenómeno por el que tus ojos tienden a ver patrones familiares en imágenes donde en realidad no existen, como ver una cara en una nube. Como puedes imaginar, debido a su constante cercanía a las vacas, Farmer John suele ver patrones relacionados con ellas en objetos cotidianos. Por ejemplo, si mira la cadena "bqessiyexbesszieb", sus ojos ignoran algunas letras y solo ve "bessiebessie".
Dada una cadena $s$, sea $B(s)$ el número máximo de copias repetidas de "bessie" que se pueden formar eliminando cero o más caracteres de $s$. En el ejemplo anterior, $B(\texttt{bqessiyexbesszieb}) = 2$.
Calcular $B(s)$ es un reto interesante, pero Farmer John quiere resolver uno aún más interesante: dada una cadena $t$ de longitud como máximo $3\cdot 10^5$ formada solo por los caracteres a-z, calcula la suma de $B(s)$ sobre todas las subcadenas contiguas $s$ de $t$.
Entrada
La entrada consiste en una cadena no vacía de longitud como máximo $3\cdot 10^5$, cuyos caracteres son todos letras minúsculas inglesas.
Salida
Imprime un único número: el número total de copias de "bessie" que se pueden formar entre todas las subcadenas de la cadena de entrada.
Ejemplos
Entrada 1
bessiebessie
Salida 1
14
Nota
Doce subcadenas contienen exactamente 1 "bessie", y 1 cadena contiene exactamente 2 copias de "bessie", por lo que el total es $12\cdot 1 + 1 \cdot 2 = 14$.
Entrada 2
abcdefghssijebessie
Salida 2
28
Subtareas
- Entradas 3-5: la cadena tiene longitud como máximo $5000$.
- Entradas 6-12: sin restricciones adicionales.
Autores del problema: Brandon Wang y Benjamin Qi