Naive pattern search algorithm for C programs

Pattern Matching in C- We have to find if a string exists in another string, for example, the string "algorithm" exists in the string in "naive algorithm". If it is found, then its location (i.e. where it is located) is displayed. We tend to create a function that takes in an array of 2 characters and returns the position if there is a match, otherwise it returns -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

We are solving this problem through naive mode search. This algorithm is useful for smaller texts. Naive is a simple and inefficient way to see where a string appears within another string by checking every possible position it may appear in to see if it exists.

The time complexity of the Naive algorithm is O(mn), where m is the size of the pattern to be searched and n is the size of the container string.

Pattern search is a very critical issue in computer science. Whenever we look for a string in a notepad/word file or browser or database or some information, Pattern search algorithms are used to display search results.

Algorithm

naive_algorithm(pattern, text)

Input− Text and pattern

Output− Where the pattern appears in the text

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

Example

Real-time demonstration

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

Output

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

The above is the detailed content of Naive pattern search algorithm for C programs. For more information, please follow other related articles on the PHP Chinese website!