Module: Fonction préfixe, fonction Z


Problem

5 /10


Fonction Z

Theory Click to read/hide

Z-fonction
Z-fonction de la chaîne S - tableau Z, dont chaque élément est Z [i ] est égal au préfixe le plus long de la sous-chaîne commençant à la position i dans la chaîne S, qui est également le préfixe de la chaîne entière Z. La valeur de la fonction Z à la position zéro est généralement soit zéro, soit la longueur de la chaîne entière.
Difficulté
O(|S| ^ 2) ou O(|S|).
 
Fonction de préfixe de la chaîne S - tableau P, chaque élément dont P[i] est égal au suffixe le plus long du sous-chaîne commençant à la position i dans la chaîne S, qui est également le suffixe de la chaîne entière S. La valeur de la fonction P à la position zéro est généralement soit zéro, soit la longueur de la chaîne entière. 
Difficulté
O(|S| ^ 2) ou O(|S|).
 
Essayez d'implémenter la fonction Z et la fonction de préfixe pour O(|S| ^ 2) .

Problem

Deux chaînes sont données - S et T. Votre tâche consiste à afficher le nombre d'occurrences du i-ième préfixe de la chaîne S dans la chaîne T.

Entrée
La première ligne contient k - le nombre de requêtes (\(k <= length( S)\)), chaîne S< /code> et la chaîne T. Ensuite, les requêtes k sont saisies, une requête pour le nombre d'occurrences du i-ème préfixe de la chaîne S dans la chaîne T.

Sortie
Sortir k lignes de réponses à la requête.

 

Exemples
2 ali balimali
3
0
# Entrée Sortie
1 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!