Algorithme de recherche de modèles naïfs pour les programmes C

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 elle renvoie -1.

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

Nous résolvons ce problème avec la recherche en mode naïf. Cet algorithme est utile pour les textes plus petits. Naive est un moyen simple et inefficace de voir où une chaîne apparaît dans une autre chaîne en vérifiant toutes les positions possibles dans lesquelles elle peut apparaître pour voir si elle existe.

La complexité temporelle de l'algorithme Naive est O(mn), où m est la taille du modèle à rechercher et n est la taille de la chaîne du conteneur.

La recherche de modèles est un problème très critique en informatique. Chaque fois que nous recherchons une chaîne dans un bloc-notes/fichier Word, un navigateur ou une base de données ou des informations, Des algorithmes de recherche de modèles sont utilisés pour afficher les résultats de la recherche.

Algorithme

naive_algorithm(pattern, text)

Entrée− Texte et motif

Sortie− Où le motif apparaît dans le texte

Start
   pat_len := pattern Size
   str_len := string size
   for i := 0 to (str_len - pat_len), do
      for j := 0 to pat_len, do
         if text[i+j] ≠ pattern[j], then
         break
   if j == patLen, then
   display the position i, as there pattern found
End

Exemple

Démonstration en temps réel

#include <stdio.h>
#include <string.h>
int main (){
   char txt[] = "tutorialsPointisthebestplatformforprogrammers";
   char pat[] = "a";
   int M = strlen (pat);
   int N = strlen (txt);
   for (int i = 0; i <= N - M; i++){
      int j;
      for (j = 0; j < M; j++)
         if (txt[i + j] != pat[j])
      break;
      if (j == M)
         printf ("Pattern matches at index %d </p><p>", i);
   }
   return 0;
}

Out put

Pattern matches at 6
Pattern matches at 25
Pattern matches at 39

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!