Module: Função de prefixo, função Z


Problem

5 /10


função Z

Theory Click to read/hide

Z-função
Z-function da string S - array Z, cada elemento do qual é Z [i] é igual ao prefixo mais longo da substring começando na posição i na string S, que também é o prefixo de toda a string Z. O valor da função Z na posição zero é geralmente zero ou o comprimento de toda a string.
Dificuldade
O(|S| ^ 2) ou O(|S|).
 
Função de prefixo da string S - array P, cada elemento do qual P[i] é igual ao sufixo mais longo do substring iniciando na posição i na string S, que também é o sufixo da string inteira S. O valor da função P na posição zero é geralmente zero ou o comprimento de toda a string. 
Dificuldade
O(|S| ^ 2) ou O(|S|).
 
Tente implementar função Z e função de prefixo para O(|S| ^ 2) .

Problem

Duas strings são dadas - S e T. Sua tarefa é exibir o número de ocorrências do i-ésimo prefixo da string S na string T.

Entrada
A primeira linha contém k - o número de consultas (\(k <= length( S)\)), string S< /code> e a string T. Em seguida, as solicitações k são inseridas, uma solicitação para o número de ocorrências do i-ésimo prefixo da string S na string T.

Saída
Saída k linhas de respostas de consulta.

 

Exemplos
# Entrada Saída
1
2 ali balimali
3
0
 2
8

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!