Naive Pattern Searching Algorithm
Naive Pattern Searching Algorithm in Data Structure
Naive pattern searching is the simplest method among other pattern searching algorithms. Although, it is more efficient than the brute force approach, however, it is not the most optimal method available. Like brute force, it also checks for all characters of the main string in order to find the pattern. Hence, its time complexity is O(m*n) where the 'm' is the size of pattern and 'n' is the size of the main string. This algorithm is helpful for smaller texts only.
The naive pattern searching algorithm does not require any pre-processing phases. We can find substring by checking once for the string. It also does not occupy extra space to perform the operation. If a match is found, the end result of the pattern matching operation will be the index of specified pattern, otherwise -1. Furthermore, this operation can return all the indices if the desired pattern appears multiple times within the main string.
Let's understand the input-output scenario of a pattern matching problem with an example −
Input: main String: "ABAAABCDBBABCDDEBCABC" pattern: "ABC" Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
Example
In the following example, we are going to demonstrate how to apply a naive approach to solve a pattern matching problem.
#include<stdio.h>
#include<string.h>
// method to search for pattern
void naiveFindPatrn(char* mainString, char* pattern, int array[], int *index) {
int patLen = strlen(pattern);
int strLen = strlen(mainString);
// outer for loop
for(int i = 0; i<=(strLen - patLen); i++) {
int j;
// to check for each character of pattern
for(j = 0; j<patLen; j++) {
if(mainString[i+j] != pattern[j])
break;
}
// to print the index of the pattern is found
if(j == patLen) {
(*index)++;
array[(*index)] = i;
}
}
}
// main method starts
int main() {
// main string
char mainString[] = "ABAAABCDBBABCDDEBCABC";
// pattern to be found
char pattern[] = "ABC";
int locArray[strlen(mainString)];
int index = -1;
naiveFindPatrn(mainString, pattern, locArray, &index);
// to print the indices
for(int i = 0; i <= index; i++) {
printf("Pattern found at position: %d
", locArray[i]);
}
return 0;
}
#include<iostream>
using namespace std;
// method to search for pattern
void naiveFindPatrn(string mainString, string pattern, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
// outer for loop
for(int i = 0; i<=(strLen - patLen); i++) {
int j;
// to check for each character of pattern
for(j = 0; j<patLen; j++) {
if(mainString[i+j] != pattern[j])
break;
}
// to print the index of the pattern is found
if(j == patLen) {
(*index)++;
array[(*index)] = i;
}
}
}
// main method starts
int main() {
// main string
string mainString = "ABAAABCDBBABCDDEBCABC";
// pattern to be found
string pattern = "ABC";
int locArray[mainString.size()];
int index = -1;
naiveFindPatrn(mainString, pattern, locArray, &index);
// to print the indices
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}
public class Main {
// method to search for pattern
static void naiveFindPatrn(String mainString, String pattern, int[] array) {
int patLen = pattern.length();
int strLen = mainString.length();
int index = 0;
// outer for loop
for(int i = 0; i <= (strLen - patLen); i++) {
int j;
// to check for each character of pattern
for(j = 0; j < patLen; j++) {
if(mainString.charAt(i+j) != pattern.charAt(j))
break;
}
// to print the index of the pattern is found
if(j == patLen) {
array[index] = i;
index++;
}
}
}
// main method starts
public static void main(String[] args) {
// main string
String mainString = "ABAAABCDBBABCDDEBCABC";
// pattern to be found
String pattern = "ABC";
int[] locArray = new int[mainString.length()];
naiveFindPatrn(mainString, pattern, locArray);
// to print the indices
for(int i = 0; i < locArray.length && locArray[i] != 0; i++) {
System.out.println("Pattern found at position: " + locArray[i]);
}
}
}
# method to search for pattern
def naiveFindPatrn(mainString, pattern):
patLen = len(pattern)
strLen = len(mainString)
indices = []
# outer for loop
for i in range(strLen - patLen + 1):
j = 0
# to check for each character of pattern
for j in range(patLen):
if mainString[i+j] != pattern[j]:
break
# to print the index of the pattern is found
if j == patLen - 1 and mainString[i+j] == pattern[j]:
indices.append(i)
return indices
# main method starts
if __name__ == "__main__":
# main string
mainString = "ABAAABCDBBABCDDEBCABC"
# pattern to be found
pattern = "ABC"
indices = naiveFindPatrn(mainString, pattern)
# to print the indices
for i in indices:
print("Pattern found at position:", i)
Output
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
