Module: Funzione prefisso, funzione Z


Problem

5 /10


Funzione Z

Theory Click to read/hide

Z-funzione
Z-funzione dalla stringa S - array Z, ogni elemento del quale è Z [i ] è uguale al prefisso più lungo della sottostringa che inizia alla posizione i nella stringa S, che è anche il prefisso dell'intera stringa Z. Il valore della funzione Z alla posizione zero è solitamente zero o la lunghezza dell'intera stringa.
Difficoltà
O(|S| ^ 2) o O(|S|).
 
Funzione di prefisso dalla stringa S - array P, ogni elemento di cui P[i] è uguale al suffisso più lungo del sottostringa a partire dalla posizione i nella stringa S, che è anche il suffisso dell'intera stringa S. Il valore della P-funzione alla posizione zero è solitamente zero o la lunghezza dell'intera stringa. 
Difficoltà
O(|S| ^ 2) o O(|S|).
 
Prova ad implementare la funzione Z e la funzione prefisso per O(|S| ^ 2) .

Problem

Sono fornite due stringhe: S e T. Il tuo compito è visualizzare il numero di occorrenze del prefisso i-esimo della stringa S nella stringa T.

Inserimento
La prima riga contiene k - il numero di query (\(k <= length( S)\)), stringa S< /code> e la stringa T. Successivamente, vengono inserite richieste k, una richiesta per il numero di occorrenze del prefisso i-esimo della stringa S nella stringa T.

Uscita
Produci k righe di risposte alla query.

 

Esempi
# Input Uscita
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!