Fonction préfixe, fonction Z


Pour résoudre ce problème, l'énumération habituelle ne fonctionnera pas, car ses asymptotique seront O(t*s). Par conséquent, pour les tâches de recherche de sous-chaînes, l'algorithme KMP (Knuth-Morris-Pratt) est utilisé.
Pour implémenter cet algorithme, la fonction de préfixe de chaîne est utilisée, il s'agit d'un tableau de nombres de longueur n (strong>s longueur), dans lequel chaque élément est la longueur maximale du plus grand suffixe propre de la sous-chaîne s, correspondant à son préfixe. Par exemple :
 
Ligne Fonction de préfixe Remarque
abababcab 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
aabaaab 0 1 0 1 2 2 3  

Algorithme de fonction de préfixe trivial avec O(n^3) asymptotique :

vecteur<int> fonction_préfixe (chaîne s) {
int n = (int ) s.length();
vecteur<int>pi(n);
pour (int i=0 ; i<n; ++i)
pour (int k=0 ; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k ;
renvoyerpi ;
}

Et maintenant, nous devons créer une fonction de préfixe pour une chaîne de la forme : & nbsp; t + # + s, où # est un caractère délimiteur qui n'est clairement pas dans le texte.  En analysant les valeurs de la fonction de préfixe après le caractère séparateur correspondant, il convient de noter que si la valeur résultante est égale à la longueur de la sous-chaîne souhaitée, son occurrence est trouvée. Par exemple, pour la chaîne "abababcab" et la sous-chaîne souhaitée "abab", la fonction de préfixe sera :
0 0 1 2 0 1 2 3 4 3 4 0 1 2 nous devons analyser les éléments de la chaîne correspondante s :
1 2 3 4 3 4 0 1 2 - il y a deux cas où la valeur est 4 ( 4e et 6e ), c'est-à-dire longueur t,  en conséquence, la réponse doit être écrite: 4 - 4 (longueur t) & nbsp; = 0 et 6 - 4 = 2. On peut voir que ce sont les bonnes réponses et la chaîne "abab" est en fait une sous-chaîne dans la chaîne "abababcab" en positions 0 et 2.

 

Training problem

(C++) Recherche de sous-chaînes, KMP, variante triviale : Début

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 ;
}

Training problem

fonction de préfixe

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) .

Training problem

Fonction Z

 
Z et le préfixe de la fonction peuvent être utilisés pour implémenter l'algorithme KMP(Knuth-Morris-Pratt) pour trouver une sous-chaîne dans une chaîne en O(|S|). L'essence de cet algorithme est la suivante : nous attribuons à la chaîne que nous voulons trouver la chaîne dans laquelle nous recherchons. Il est fortement souhaitable de mettre un caractère séparateur entre ces lignes, c'est-à-dire un caractère qui n'apparaît sur aucune ligne (généralement #).

Training problem

Chiffrer