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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.