Naive Algorithm for Pattern Searching in C++

By Dinesh Kumar

In this tutorial, we are going to learn about the Naive Algorithm for pattern searching and implementing it in C++ program. So keep following this tutorial…

Let’s see an example first:-
You have given two strings pattern string and a text string. You have to print the positions of occurrences of pattern in the text by comparing each letter of pattern with the text string.

Input:-
text=”I’m a coder, competitive coder!!”
pattern=”coder”

Output:-
Found at index 6
Found at index 25

Algorithm

Naive pattern matching algorithm is not a very efficient algorithm. It takes O(n*m) time for searching in worst case. Each letter of pattern is searched in text. It takes two loops for searching every possibility.

Algorithm:-

1. n <- len(text)
2. m <- len(pattern)
3. for i=0 to n-m
4.     for j=0 to m
5.          if text[i+j] != pattern[j]
6.              break
7.     if j==m
8.         print "Found at index", i

C++ Program for Naive Algorithm for Pattern Searching

So, here is the C++ implementation of the above algorithm:-

#include <bits/stdc++.h> 
using namespace std; 


/*===========================================
     FUNCTION FOR PATTERN SEARCHING
============================================*/
void naive_algorithm(string text,string pattern) 
{ 
  //length of text string stored in n
  int n = text.length();
  //length of pattern string stored in m 
  int m = pattern.length(); 
  int i,j;
  //Loop for text
  for (i = 0; i <= n-m; i++) 
  { 
    //Loop for pattern
    for (j = 0; j < m; j++) 
    {
      if (text[i+j]!= pattern[j]) 
        break; 
    }
   //if j==pattern length means pattern found
    if (j == m) 
      cout<<"Found at index "<<i<<endl; 
  } 
} 

/*===========================================
                MAIN FUNCTION
============================================*/ 
int main() 
{ 
  string pattern,text;
  text = "I'm a coder, competitive coder!!"; 
  pattern = "coder"; 
  naive_algorithm(text, pattern); 
  return 0; 
} 

Output:-

Found at index 6
Found at index 25

Thanks for reading this tutorial. I hope it helps you !!