Maison > Article > développement back-end > 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.
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
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; }
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!