Module: Präfix-Funktion, Z-Funktion


Problem

5 /10


Z-Funktion

Theory Click to read/hide

Z- Funktion
Z- Funktion von der Linie S - eine Masse Zjedes Element, dessen Z[i] ist das längste Vorfix des Unterbaus ausgehend von der Position i in Zeile Sdie gleichzeitig eine Vorstigung der gesamten Leitung ist Z~ Importance ~ Z- Brunnen in einer Nullstellung in der Regel gleich oder Null, oder die Länge der gesamten Linie.
Komplexität
O(|S| ^ 2) oder O(|S|)♪
Vorfix-Funktion aus der Linie S - eine Masse Pjedes Element, dessen P[i] ist das längste Soufffix des Unterbaus ausgehend von der Position i in Zeile Sdie gleichzeitig ein Souffix der ganzen Linie ist S~ Importance ~ P- Funktionen. in einer Nullstellung üblicherweise gleich Null oder die Länge der gesamten Linie.
Komplexität
O(|S| ^ 2) oder O(|S|)♪
Versuchen Sie, es passieren zu lassen. Z-функцию und Vorfix-Funktionfür O(|S| ^ 2)♪

Problem

Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

Выходные данные
Вывести k строк с ответами на запросы.

 

Примеры
№ Входные данные Выходные данные
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!