Module: Función de prefijo, función Z


Problem

5 /10


Función Z

Theory Click to read/hide

Z-función
Z-función de la cadena S - matriz Z, cada elemento del cual es Z [i ] es igual al prefijo más largo de la subcadena que comienza en la posición i en la cadena S, que también es el prefijo de la cadena completa Z. El valor de la función Z en la posición cero suele ser cero o la longitud de la cadena completa.
Dificultad
O(|S| ^ 2) o O(|S|).
 
Función de prefijo de la cadena S - matriz P, cada elemento del cual P[i] es igual al sufijo más largo del subcadena que comienza desde la posición i en la cadena S, que también es el sufijo de la cadena completa S. El valor de la función P en la posición cero suele ser cero o la longitud de la cadena completa. 
Dificultad
O(|S| ^ 2) o O(|S|).
 
Intente implementar función Z y función de prefijo para O(|S| ^ 2) .

Problem

Se dan dos cadenas: S y T. Su tarea es mostrar el número de ocurrencias del prefijo i-th de la cadena S en la cadena T.

Entrada
La primera línea contiene k - el número de consultas (\(k <= length( S)\)), cadena S< /code> y la cadena T. A continuación, se ingresan las solicitudes k, una solicitud del número de ocurrencias del prefijo i-th de la cadena S en la cadena T.

Salida
Generar k líneas de respuestas de consulta.

 

Ejemplos

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1
2 ali balimali
3
0
 2
8