Étant donné un texte txt[0 . . . N-1] et un modèle lit[0 . . . M-1] , écrivez une fonction search(char pat[], char txt[]) qui imprime toutes les occurrences de pat[] dans txt[]. Vous pouvez supposer que N >M .

Exemples:

Saisir: txt[] = CECI EST UN TEXTE DE TEST, pat[] = TEST
Sortir: Modèle trouvé à l'index 10

Saisir: txt[] = VOS PÈRES
pat[] = AABA
Sortir: Modèle trouvé à l'index 0, Modèle trouvé à l'index 9, Modèle trouvé à l'index 12

Arrivées de motif dans le texte

Nous avons discuté de l'algorithme de recherche de modèles Naive dans le post précédent . La complexité dans le pire des cas de l’algorithme Naive est O(m(n-m+1)). La complexité temporelle de l'algorithme KMP est O(n+m) dans le pire des cas.

Recherche de modèles KMP (Knuth Morris Pratt) :

Le Algorithme de recherche de modèles naïf ne fonctionne pas bien dans les cas où nous voyons de nombreux caractères correspondants suivis d'un caractère incompatible.

Exemples:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (pas le pire des cas, mais un mauvais cas pour Naive)

L'algorithme de correspondance KMP utilise la propriété dégénérative (modèle ayant les mêmes sous-modèles apparaissant plus d'une fois dans le modèle) du modèle et améliore la complexité du pire des cas pour O(n+m) .

L’idée de base derrière l’algorithme de KMP est la suivante : chaque fois que nous détectons une disparité (après quelques correspondances), nous connaissons déjà certains caractères dans le texte de la fenêtre suivante. Nous profitons de ces informations pour éviter de faire correspondre les caractères dont nous savons qu'ils correspondront de toute façon.

Aperçu de la correspondance

txt = AAAAABAAABA
tapoter = AAAA
Nous comparons la première fenêtre de SMS avec le même

txt = AAAA PÈRE
même = AAAA [Position initiale]
Nous trouvons une correspondance. C'est la même chose que Correspondance naïve de chaînes .

Dans l'étape suivante, nous comparons la fenêtre suivante de SMS avec le même .

txt = AAAAA DÉTRUIRE
même = AAAA [Motif décalé d'une position]

C'est là que KMP effectue l'optimisation sur Naive. Dans cette deuxième fenêtre, on compare uniquement le quatrième A du motif
avec le quatrième caractère de la fenêtre actuelle du texte pour décider si la fenêtre actuelle correspond ou non. Puisque nous savons
les trois premiers caractères correspondront de toute façon, nous avons ignoré la correspondance des trois premiers caractères.

Besoin de prétraitement ?

Une question importante découle de l’explication ci-dessus : comment savoir combien de caractères doivent être ignorés. Pour savoir cela,
nous pré-traitons le modèle et préparons un tableau d'entiers lps[] qui nous indique le nombre de caractères à ignorer

Présentation du prétraitement :

• L'algorithme KMP prétraite pat[] et construit un auxiliaire lps[] de taille m (identique à la taille du motif) qui est utilisé pour sauter des caractères lors de la correspondance.
• Nom lps indique le préfixe propre le plus long qui est également un suffixe. Un préfixe approprié est un préfixe avec une chaîne entière non autorisée. Par exemple, les préfixes de ABC sont , A, AB et ABC. Les préfixes appropriés sont , A et AB. Les suffixes de la chaîne sont , C, BC et ABC.
• Nous recherchons des lps dans les sous-motifs. Plus clairement, nous nous concentrons sur les sous-chaînes de motifs qui sont à la fois préfixe et suffixe.
• Pour chaque sous-modèle pat[0..i] où i = 0 à m-1, lps[i] stocke la longueur du préfixe propre correspondant maximum qui est également un suffixe du sous-modèle pat[0..i ].

lps[i] = le préfixe propre le plus long de pat[0..i] qui est également un suffixe de pat[0..i].

Note: lps[i] pourrait également être défini comme le préfixe le plus long qui est également un suffixe approprié. Nous devons l'utiliser correctement au même endroit pour nous assurer que la sous-chaîne entière n'est pas prise en compte.

Exemples de construction lps[] :

Pour le modèle AAAA, lps[] vaut [0, 1, 2, 3]

Pour le modèle ABCDE, lps[] vaut [0, 0, 0, 0, 0]

Pour le modèle AABAACAABAA, lps[] vaut [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Pour le modèle AAACAAAAAC, lps[] vaut [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Pour le modèle AAABAAA, lps[] vaut [0, 1, 2, 0, 1, 2, 3]

Algorithme de prétraitement :

Dans la partie prétraitement,

• Nous calculons les valeurs dans lps[] . Pour ce faire, nous gardons une trace de la longueur de la valeur de suffixe de préfixe la plus longue (nous utilisons seulement variable à cet effet) pour l'index précédent
• Nous initialisons lps[0] et seulement comme 0.
• Si pat[len] et des lits match, nous incrémentons seulement par 1 et attribuez la valeur incrémentée à lps[i].
• Si pat[i] et pat[len] ne correspondent pas et que len n'est pas 0, nous mettons à jour len en lps[len-1]
• Voir calculLPSArray() dans le code ci-dessous pour plus de détails

Illustration du prétraitement (ou construction de lps[]) :

pat[] = AAAAAAA

propriétés acides dans les dbms

=> len = 0, je = 0 :

• lps[0] vaut toujours 0, on passe à i = 1

=> len = 0, je = 1 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• stockez-le dans lps[i] et faites i++.
• Définir len = 1, lps[1] = 1, i = 2

=> len = 1, je = 2 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• stockez-le dans lps[i] et faites i++.
• Définir len = 2, lps[2] = 2, i = 3

=> len = 2, je = 3 :

• Puisque pat[len] et pat[i] ne correspondent pas et que len> 0,
• Définir len = lps[len-1] = lps[1] = 1

=> len = 1, je = 3 :

• Puisque pat[len] et pat[i] ne correspondent pas et que len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, je = 3 :

• Puisque pat[len] et pat[i] ne correspondent pas et que len = 0,
• Définir lps[3] = 0 et i = 4

=> len = 0, je = 4 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• Stockez-le dans lps[i] et faites i++.
• Définir len = 1, lps[4] = 1, i = 5

=> len = 1, je = 5 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• Stockez-le dans lps[i] et faites i++.
• Définir len = 2, lps[5] = 2, i = 6

=> len = 2, je = 6 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• Stockez-le dans lps[i] et faites i++.
• len = 3, lps[6] = 3, je = 7

=> len = 3, je = 7 :

• Puisque pat[len] et pat[i] ne correspondent pas et que len> 0,
• Définir len = lps[len-1] = lps[2] = 2

=> len = 2, je = 7 :

• Puisque pat[len] et pat[i] correspondent, faites len++,
• Stockez-le dans lps[i] et faites i++.
• len = 3, lps[7] = 3, je = 8

Nous nous arrêtons ici car nous avons construit l'intégralité du lps[].

Implémentation de l'algorithme KMP :

Contrairement au Algorithme naïf , où nous faisons glisser le motif d'un et comparons tous les caractères à chaque décalage, nous utilisons une valeur de lps[] pour décider des prochains caractères à faire correspondre. L'idée est de ne pas faire correspondre un personnage dont nous savons qu'il correspondra de toute façon.

Comment utiliser lps[] pour décider des prochaines positions (ou connaître le nombre de caractères à sauter) ?

• On commence la comparaison de pat[j] avec j = 0 avec les caractères de la fenêtre de texte courante.
• Nous continuons à faire correspondre les caractères txt[i] et pat[j] et continuons à incrémenter i et j tandis que pat[j] et txt[i] restent correspondant à .
• Quand on voit un décalage
  • Nous savons que les caractères pat[0..j-1] correspondent à txt[i-j…i-1] (Notez que j commence par 0 et ne l'incrémente que lorsqu'il y a une correspondance).
  • Nous savons également (d'après la définition ci-dessus) que lps[j-1] est le nombre de caractères de pat[0…j-1] qui sont à la fois un préfixe et un suffixe appropriés.
  • Des deux points ci-dessus, nous pouvons conclure que nous n'avons pas besoin de faire correspondre ces caractères lps[j-1] avec txt[i-j…i-1] car nous savons que ces caractères correspondront de toute façon. Considérons l'exemple ci-dessus pour comprendre cela.

Ci-dessous l'illustration de l'algorithme ci-dessus :

Considérez txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Si nous suivons le processus de construction LPS ci-dessus, alors lps[] = {0, 1, 2, 3}

-> je = 0, j = 0 : txt[i] et pat[j] correspondent, fais i++, j++

-> je = 1, j = 1 : txt[i] et pat[j] correspondent, fais i++, j++

-> je = 2, j = 2 : txt[i] et pat[j] correspondent, fais i++, j++

-> je = 3, j = 3 : txt[i] et pat[j] correspondent, fais i++, j++

-> je = 4, j = 4 : Puisque j = M, imprimez le motif trouvé et réinitialisez j, j = lps[j-1] = lps[3] = 3

Ici contrairement à l’algorithme Naive, nous ne faisons pas correspondre les trois premiers
caractères de cette fenêtre. La valeur de lps[j-1] (à l'étape ci-dessus) nous a donné l'index du prochain caractère à correspondre.

-> je = 4, j = 3 : txt[i] et pat[j] correspondent, fais i++, j++

-> je = 5, j = 4 : Puisque j == M, imprimez le motif trouvé et réinitialisez j, j = lps[j-1] = lps[3] = 3
Encore une fois, contrairement à l'algorithme Naive, nous ne faisons pas correspondre les trois premiers caractères de cette fenêtre. La valeur de lps[j-1] (à l'étape ci-dessus) nous a donné l'index du prochain caractère à correspondre.

-> je = 5, j = 3 : txt[i] et pat[j] ne correspondent PAS et j> 0, changez uniquement j. j = lps[j-1] = lps[2] = 2

-> je = 5, j = 2 : txt[i] et pat[j] ne correspondent PAS et j> 0, changez uniquement j. j = lps[j-1] = lps[1] = 1

-> je = 5, j = 1 : txt[i] et pat[j] ne correspondent PAS et j> 0, changez uniquement j. j = lps[j-1] = lps[0] = 0

-> je = 5, j = 0 : txt[i] et pat[j] ne correspondent PAS et j vaut 0, nous faisons i++.

-> je = 6, j = 0 : txt[i] et pat[j] correspondent, faites i++ et j++

-> je = 7, j = 1 : txt[i] et pat[j] correspondent, faites i++ et j++

Nous continuons ainsi jusqu'à ce qu'il y ait suffisamment de caractères dans le texte pour être comparés aux caractères du motif…

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

C++

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) {  $M = strlen($pat);  $N = strlen($txt);  // create lps[] that will hold the longest prefix suffix  // values for pattern  $lps=array_fill(0,$M,0);  // Preprocess the pattern (calculate lps[] array)  computeLPSArray($pat, $M, $lps);  $i = 0; // index for txt[]  $j = 0; // index for pat[]  while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Motif trouvé à l'index '.($i - $j));  $j = $lps[$j - 1];  } // non-concordance après j correspond à else if ($i<$N && $pat[$j] != $txt[$i]) {  // Do not match lps[0..lps[j-1]] characters,  // they will match anyway  if ($j != 0)  $j = $lps[$j - 1];  else  $i = $i + 1;  }  } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) {  // Length of the previous longest prefix suffix  $len = 0;  $lps[0] = 0; // lps[0] is always 0  // The loop calculates lps[i] for i = 1 to M-1  $i = 1;  while ($i <$M) {  if ($pat[$i] == $pat[$len]) {  $len++;  $lps[$i] = $len;  $i++;  }  else // (pat[i] != pat[len])  {  // This is tricky. Consider the example.  // AAACAAAA and i = 7. The idea is similar  // to search step.  if ($len != 0) {  $len = $lps[$len - 1];  // Also, note that we do not increment  // i here  }  else // if (len == 0)  {  $lps[$i] = 0;  $i++;  }  }  } } // Driver program to test above function  $txt = 'ABABDABACDABABCABAB';  $pat = 'ABABCABAB';  KMPSearch($pat, $txt);   // This code is contributed by chandan_jnu ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortir  
hôte Linux
 
Found pattern at index 10>
 
    Complexité temporelle :    O(N+M) où N est la longueur du texte et M est la longueur du motif à trouver.  
    Espace auxiliaire :    O(M)