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.