Module: Fonction préfixe, fonction Z


Problem

2 /10


fonction de préfixe

Theory Click to read/hide

Après avoir optimisé la fonction de préfixe (pour plus de détails ici ), nous obtenons l'algorithme final avec O(n) asymptotique :

vecteur<int> fonction_préfixe (chaîne s) {
int n = (int ) s.length();
vecteur<int>pi(n);
pour (int i=1 ; i<n; ++i) {
int j = pi[i-1< /span>] ;
tandis que (j > 0 && s[i] != s[j])
j = pi[j-1] ;
si (s[i] == s[j]) ++j ;
pi[i] = j ;
}
renvoyerpi ;
}

Problem

Soit une chaîne non vide S dont la longueur N ne dépasse pas \(10^6\). Nous supposerons que les éléments de la chaîne sont numérotés de 1 à N.
 
Pour chaque position du caractère i dans la chaîne, nous serons intéressés par la sous-chaîne qui se termine à cette position et correspond à un début de la chaîne entière. De manière générale, il y aura plusieurs sous-chaînes de ce type, au moins deux. Le plus long d'entre eux a pour longueur i, nous ne nous y intéresserons pas. Et nous nous intéresserons à la plus longue des sous-chaînes restantes (notez qu'une telle sous-chaîne existe toujours - dans le cas extrême, si rien d'autre n'est trouvé, une sous-chaîne vide fera l'affaire).
 
La valeur de la fonction de préfixe \(\pi[i]\) sera la longueur de cette sous-chaîne.
 
La fonction de préfixe est utilisée dans divers algorithmes de traitement de chaînes. En particulier, il peut être utilisé pour résoudre rapidement le problème de trouver l'occurrence d'une chaîne dans une autre ("recherche d'un motif dans le texte").
 
Requis pour tous les i de 1 à N pour calculer \(\pi[i ] \).
 
Entrée
Une chaîne de longueur N, \(0 < N <= 10^6\), composée de petites lettres latines .
 
Sortie
Numéros N de sortie &mdash ; valeurs de fonction de préfixe pour chaque position, séparées par des espaces.
 

 

Exemples
# Entrée Sortie
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4

time 1000 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!