The naive algorithm for pattern searching
A naive algorithm is used for pattern matching. It is a straightforward and easy-to-implement algorithm that makes it popular among other algorithms. It is used to find all the matching occurrences of specified text in the given string. It is useful for small texts and doesn't occupy extra memory space for searching and matching.
Example
Let's see a sample input and output of this algorithm.
Working
Let's say we get a text string with length m and a pattern with length n. The naive approach checks all the possible placements of pattern[1-n] relative to text[1-m]. Afterward, we slide the pattern over the text one by one and test if the pattern exists. If a match is found, slide by one again to check for all remaining matches. Let's see the working of the naive algorithm below:
Beginpattern_len := pattern Sizetext_Len := string sizefor i := 0 to (text_len - pattern_len)for j := 0 to pattern_lenif text[i+j] ≠ pattern[j], thenbreak the loopif j == pattern_len, thendisplay the position i, as there is patternEnd
Note: We can find all the substrings by checking once in the string.
Implementation
Let's see step by step implementation of the naive algorithm in C++:
#include <bits/stdc++.h>using namespace std;void naive_algo(char* pattern, char* text){int pat_len = strlen(pattern);int text_len = strlen(text);for (int i = 0; i <= text_len - pat_len; i++) { //outer loopint j;//For current index i, check patternfor (j = 0; j < pat_len; j++) //inner loopif (text[i + j] != pattern[j])break;if (j== pat_len) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]cout << "Pattern found at index " << i << endl;}}// Driver's Codeint main(){char text[] = "I love educative";char pattern[] = "educative";// Function callnaive_algo(pattern, text);return 0;}
Code explanation
Lines 4–7: We define the naive_algo() function to perform pattern searching. We initialize two variables pat_length and text_len with the length of pattern and text string, respectively.
Lines 9–13: We create two loops, an outer and an inner loop, to traverse the string and match the pattern for each character.
Lines 14–18: Inner loop matches the text character with the first character, and if it doesn't match, then break the loop. If all characters are matched with pattern , print that index.
Time complexity
The time complexity for this approach is
Space complexity
The space complexity for this approach is
