Naive Algorithm for Pattern Searching in C++
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 !!
Leave a Reply