|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
F - Sufijos b-semejantes
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Fito está estudiando las relaciones entre dos palabras y encuentra un concepto interesante. Se dice que dos palabras son $b$-semejantes si ambas tienen un prefijo común de longitud mayor o igual que $b$. Este concepto se puede usar para agrupar palabras que se derivan de la misma raíz.
Fito quiere ahora aplicar esta relación, pero entre la palabra y sus sufijos. Queremos saber para un texto $S$ cuantos sufijos son $b$-semejantes con él para distintos valores de $b$.
Input
La primera línea de la entrada es un entero $T (1 \leq T \leq 10)$ que indica la cantidad de casos de pruebas. La primera línea de cada caso de prueba contiene el texto $S(1 \leq |S| \leq 10^5)$. El texto S está formado por letras minúsculas del alfabeto latino. La siguiente línea es un entero $M (1 \leq M \leq 10^5)$ que representa la cantidad de valores de $b$. Después le sigue una línea con $M$ valores separados por un espacio, cada uno es un valor de $b (0 \leq b \leq 10^5)$.
Output
Por cada valor de $b$ se debe responder cuantos sufijos de $S$ son b-semejantes con él. Todas las respuestas de un caso de prueba deben aparecer en una línea separadas por un espacio.
Sample test(s)
Input
1
abcaba
2
1 2
Output
3 2