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

Qu'est-ce que l'algorithme Rabin-Karp ?

L'algorithme Rabin-Karp est un algorithme de correspondance de modèles de chaîne qui recherche efficacement les occurrences d'un modèle dans un texte plus grand. Il a été développé par Michael O. Rabin et Richard M. Karp en 1987.

L'algorithme utilise une technique de hachage pour comparer les valeurs de hachage du modèle et des sous-chaînes du texte. Cela fonctionne comme suit :

• Calculez la valeur de hachage du motif et de la première fenêtre du texte.

• Faites glisser le motif sur le texte une position à la fois et comparez les valeurs de hachage.

• Si les valeurs de hachage correspondent, comparez les caractères du motif et la fenêtre actuelle du texte pour confirmer la correspondance.

• S'il y a une correspondance, enregistrez la position/l'index de la correspondance.

• Calculez la valeur de hachage pour la fenêtre suivante du texte à l'aide d'une fonction de hachage roulant.

• Répétez les étapes 3 à 5 jusqu'à ce que toutes les positions du texte aient été vérifiées.

La fonction de hachage roulant met à jour efficacement la valeur de hachage pour chaque nouvelle fenêtre en soustrayant la contribution du premier caractère de la fenêtre précédente et en ajoutant la contribution du caractère suivant dans la nouvelle fenêtre. Cela permet d'éviter de recalculer la valeur de hachage à partir de zéro pour chaque fenêtre, ce qui rend l'algorithme plus efficace.

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

<?php

function rabinKarp($pattern, $text)
{
   $d = 256; // Number of characters in the input alphabet
   $q = 101; // A prime number

   $M = strlen($pattern);
   $N = strlen($text);
   $p = 0; // Hash value for pattern
   $t = 0; // Hash value for text
   $h = 1;

   // Calculate the hash value of pattern and first window of text
   for ($i = 0; $i < $M - 1; $i++)
      $h = ($h * $d) % $q;

   for ($i = 0; $i < $M; $i++) {
      $p = ($d * $p + ord($pattern[$i])) % $q;
      $t = ($d * $t + ord($text[$i])) % $q;
   }

   // Slide the pattern over text one by one
   for ($i = 0; $i <= $N - $M; $i++) {

      // Check the hash values of current window of text and pattern
      // If the hash values match, then only check for characters one by one
      if ($p == $t) {
         $match = true;

         // Check for characters one by one
         for ($j = 0; $j < $M; $j++) {
            if ($text[$i + $j] != $pattern[$j]) {
               $match = false;
               break;
            }
         }

         // Pattern found
         if ($match)
            echo "Pattern found at index " . $i . "<br>";
      }

      // Calculate the hash value for the next window of text
      if ($i < $N - $M) {
         $t = ($d * ($t - ord($text[$i]) * $h) + ord($text[$i + $M])) % $q;

         // If the calculated hash value is negative, make it positive
         if ($t < 0)
            $t = $t + $q;
      }
   }
}

// Example usage
$text = "ABCABCABCABCABC";
$pattern = "BC";
rabinKarp($pattern, $text);
?>

Sortie

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Explication du code

Le code PHP implémente l'algorithme Rabin-Karp pour la recherche de modèles. Il prend un modèle et un texte comme entrées et recherche les occurrences du modèle dans le texte. L'algorithme calcule les valeurs de hachage pour le modèle et la première fenêtre du texte. Il fait ensuite glisser le motif sur le texte, en comparant les valeurs de hachage de la fenêtre actuelle et le motif. Si les valeurs de hachage correspondent, il vérifie en outre les caractères un par un. Si une correspondance est trouvée, il imprime l'index où le modèle est trouvé. L'algorithme utilise une fonction de hachage glissant pour mettre à jour efficacement la valeur de hachage pour chaque fenêtre. Le code démontre l'utilisation de l'algorithme en recherchant le modèle « BC » dans le texte « ABCABCABCABCABC ».

Conclusion

En conclusion, le programme PHP implémente efficacement l'algorithme Rabin-Karp pour la recherche de modèles. En utilisant une fonction de hachage roulant et en comparant les valeurs de hachage, l'algorithme recherche efficacement les occurrences d'un modèle dans un texte plus grand. Le programme identifie correctement les indices où le modèle se trouve dans le texte et affiche les résultats. Avec une structure claire et des calculs de hachage appropriés, le programme démontre la fonctionnalité et l'utilité de l'algorithme Rabin-Karp pour la recherche de modèles en PHP.

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!