Naiver Mustersuchalgorithmus für C-Programme

Mustervergleich in C - Wir müssen herausfinden, ob ein String in einem anderen String existiert, zum Beispiel existiert der String „Algorithmus“ im String „naiver Algorithmus“. Wenn es gefunden wird, wird sein Standort (d. h. wo es sich befindet) angezeigt. Wir neigen dazu, eine Funktion zu erstellen, die ein Array von 2 Zeichen aufnimmt und bei einer Übereinstimmung die Position zurückgibt, andernfalls -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

Wir lösen dieses Problem mit der Suche im naiven Modus. Dieser Algorithmus ist für kleinere Texte nützlich. Naiv ist eine einfache und ineffiziente Methode, um festzustellen, wo eine Zeichenfolge in einer anderen Zeichenfolge vorkommt, indem jede mögliche Position überprüft wird, an der sie möglicherweise vorhanden ist.

Die zeitliche Komplexität des Naive-Algorithmus beträgt O(mn), wobei m die Größe des zu durchsuchenden Musters und n die Größe der Containerzeichenfolge ist.

Mustersuche ist ein sehr kritisches Problem in der Informatik. Immer wenn wir in einem Editor, einer Word-Datei, einem Browser oder einer Datenbank nach einer Zeichenfolge oder anderen Informationen suchen, Zur Anzeige von Suchergebnissen werden Mustersuchalgorithmen verwendet.

Algorithmus

naiver_Algorithmus (Muster, Text)

Eingabe− Text und Muster

Ausgabe− Wo das Muster im Text erscheint

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

Beispiel

Echtzeitdemonstration

#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;
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonNaiver Mustersuchalgorithmus für C-Programme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!