Eco síncrono#13118
Se dan dos cadenas y formadas por letras minúsculas del alfabeto inglés.
Para una cadena no vacía , sean p_1<p_2<\ldots<p_k todas las posiciones iniciales de sus ocurrencias en , y sean q_1<q_2<\ldots<q_m todas las posiciones iniciales de sus ocurrencias en . Las posiciones se numeran a partir de .
Decimos que es síncrona si k=m\ge 3 y existe un entero tal que
En otras palabras, al desplazar todas las ocurrencias de en una de las cadenas la misma cantidad, estas coinciden con todas sus ocurrencias en la otra cadena. El desplazamiento puede ser positivo, negativo o cero, y puede ser distinto para distintas cadenas .
Halle la cantidad de cadenas síncronas no vacías distintas. Dos cadenas son distintas si tienen longitudes diferentes o difieren en al menos un carácter. Las ocurrencias pueden solaparse.
La primera línea contiene y la segunda línea contiene (1\le |s|,|t|\le 2\cdot 10^5). Ambas cadenas contienen únicamente letras minúsculas del alfabeto inglés.
Imprima un entero — la cantidad de cadenas síncronas no vacías distintas.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, las seis cadenas adecuadas son a, b, c, ab, bc y abc. En particular, abc aparece en en las posiciones y en en las posiciones , por lo que su desplazamiento es d=1.
En el segundo ejemplo, a aparece tres veces en cada cadena, pero sus posiciones iniciales son y . Ningún desplazamiento único hace que estos conjuntos coincidan. Ninguna otra cadena aparece al menos tres veces en ambas cadenas.
En el tercer ejemplo, las cadenas adecuadas son a, aa y aaa.
Subtarea ( puntos): |s|,|t|\le 12.
Subtarea ( puntos): |s|,|t|\le 100.
Subtarea ( puntos): |s|,|t|\le 2000.
Subtarea ( puntos): s=t.
Subtarea ( puntos): \min(|s|,|t|)\le 200.
Subtarea ( puntos): sin restricciones adicionales.