C++ Program to Perform Naive String Matching
Posted by Superadmin on August 10 2022 04:11:52

C++ Program to Perform Naive String Matching

 

 

This is a C++ Program to perform Naive String matching algorithm. In computer science, string searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text.

 

Here is source code of the C++ Program to Perform Naive String Matching. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<string.h>
  3. void search(char *pat, char *txt)
  4. {
  5.     int M = strlen(pat);
  6.     int N = strlen(txt);
  7.  
  8.     /* A loop to slide pat[] one by one */
  9.     for (int i = 0; i <= N - M; i++)
  10.     {
  11.         int j;
  12.  
  13.         /* For current index i, check for pattern match */
  14.         for (j = 0; j < M; j++)
  15.         {
  16.             if (txt[i + j] != pat[j])
  17.                 break;
  18.         }
  19.         if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
  20.         {
  21.             printf("Pattern found at index %d \n", i);
  22.         }
  23.     }
  24. }
  25.  
  26. /* Driver program to test above function */
  27. int main()
  28. {
  29.     char *txt = "AABAACAADAABAAABAA";
  30.     char *pat = "AABA";
  31.     search(pat, txt);
  32.     return 0;
  33. }

Output:

$ g++ StringMatchingNaive.cpp
$ a.out
 
Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13 
------------------
(program exited with code: 0)
Press return to continue