Programme C de l'algorithme Rabin-Karp pour la recherche de modèles

Correspondance de motifs en C - Nous devons trouver si une chaîne existe dans une autre chaîne, par exemple, la chaîne "algorithme" existe dans la chaîne "algorithme naïf". S'il est trouvé, alors son emplacement (c'est-à-dire l'endroit où il se trouve) est affiché. Nous avons tendance à créer une fonction qui prend un tableau de 2 caractères et renvoie la position s'il y a une correspondance Sinon, -1 est renvoyé.

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

Rabin-Karp est un autre algorithme de recherche de modèles. Juste une correspondance de chaîne Algorithme proposé par Rabin et Karp pour trouver des modèles plus efficacement Chemin. Comme l'algorithme naïf, il vérifie également les modèles en déplaçant la fenêtre Il recherche les hachages un par un, mais n'a pas besoin de vérifier tous les caractères dans tous les cas. Lorsque les hachages correspondent, chaque caractère est vérifié. De cette façon, il n’y a qu’une seule comparaison par sous-séquence de texte, ce qui en fait un algorithme de recherche de modèles plus efficace.

Temps de prétraitement - O(m)

La complexité temporelle de l'algorithme de Rabin-Karp est O(m+n), mais dans le pire des cas, Il est O(mn).

Algorithme

rabinkarp_algo(text,pattern,prime)

Input

rabinkarp_algo(text,pattern,prime)

Inputstrong>− Texte et motif. Trouvez un autre nombre premier à la position de hachage

Output− Trouvez la position du motif

Start
   pat_len := pattern Length
   str_len := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set
for index i of all character in the pattern, do
   h := (h*maxChar) mod prime
for all character index i of pattern, do
   patHash := (maxChar*patHash + pattern[i]) mod prime
   strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
   if patHash = strHash, then
      for charIndex := 0 to pat_len -1, do
         if text[i+charIndex] ≠ pattern[charIndex], then
         break
if charIndex = pat_len, then
   print the location i as pattern found at i position.
if i < (str_len - pat_len), then
   strHash := (maxChar*(strHash &ndash; text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

Exemple

Démo en direct

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string </p><p>");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched </p><p>");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number </p><p>");
   scanf ("%d", &q);
   int M = strlen (pat);
   int N = strlen (txt);
   int i, j;
   int p = 0;
   int t = 0;
   int h = 1;
   for (i = 0; i < M - 1; i++)
      h = (h * d) % q;
   for (i = 0; i < M; i++){
      p = (d * p + pat[i]) % q;
      t = (d * t + txt[i]) % q;
   }
   for (i = 0; i <= N - M; i++){
      if (p == t){
         for (j = 0; j < M; j++){
            if (txt[i + j] != pat[j])
            break;
         }
         if (j == M)
            printf ("Pattern found at index %d </p><p>", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

Output

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!