Naive algorithm for Pattern Searching
Last Updated :
20 Oct, 2023
Given text string with length n and a pattern with length m, the task is to prints all occurrences of pattern in text.
Note: You may assume that n > m.
Examples:
Input: text = “THIS IS A TEST TEXT”, pattern = “TEST”
Output: Pattern found at index 10
Input: text = “AABAACAADAABAABA”, pattern = “AABA”
Output: Pattern found at index 0, Pattern found at index 9, Pattern found at index 12
Pattern searching
Naive Pattern Searching algorithm:
Slide the pattern over text one by one and check for a match. If a match is found, then slide by 1 again to check for subsequent matches.
C++
#include <bits/stdc++.h>
using namespace std;
void search(string& pat, string txt)
{
int M = pat.size();
int N = txt.size();
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j
== M)
cout << "Pattern found at index " << i << endl;
}
}
int main()
{
string txt = "AABAACAADAABAAABAA";
string pat = "AABA";
search(pat, txt);
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
void search(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j
== M)
printf("Pattern found at index %d \n", i);
}
}
int main()
{
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
search(pat, txt);
return 0;
}
|
Java
public class NaiveSearch {
static void search(String pat, String txt)
{
int l1 = pat.length();
int l2 = txt.length();
int i = 0, j = l2 - 1;
for (i = 0, j = l2 - 1; j < l1;) {
if (txt.equals(pat.substring(i, j + 1))) {
System.out.println("Pattern found at index "
+ i);
}
i++;
j++;
}
}
public static void main(String args[])
{
String pat = "AABAACAADAABAAABAA";
String txt = "AABA";
search(pat, txt);
}
}
|
Python3
def search(pat, txt):
M = len(pat)
N = len(txt)
for i in range(N - M + 1):
j = 0
while(j < M):
if (txt[i + j] != pat[j]):
break
j += 1
if (j == M):
print("Pattern found at index ", i)
if __name__ == '__main__':
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
|
C#
using System;
class GFG {
public static void search(String txt, String pat)
{
int M = pat.Length;
int N = txt.Length;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
Console.WriteLine("Pattern found at index "
+ i);
}
}
public static void Main()
{
String txt = "AABAACAADAABAAABAA";
String pat = "AABA";
search(txt, pat);
}
}
|
Javascript
function search(txt, pat)
{
let M = pat.length;
let N = txt.length;
for (let i = 0; i <= N - M; i++) {
let j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
document.write("Pattern found at index " + i + "</br>");
}
}
let txt = "AABAACAADAABAAABAA";
let pat = "AABA";
search(txt, pat);
|
PHP
<?php
function search($pat, $txt)
{
$M = strlen($pat);
$N = strlen($txt);
for ($i = 0; $i <= $N - $M; $i++)
{
for ($j = 0; $j < $M; $j++)
if ($txt[$i + $j] != $pat[$j])
break;
if ($j == $M)
echo "Pattern found at index ", $i."\n";
}
}
$txt = "AABAACAADAABAAABAA";
$pat = "AABA";
search($pat, $txt);
?>
|
Output
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Time Complexity: O(N2)
Auxiliary Space: O(1)
Complexity Analysis of Naive algorithm for Pattern Searching:
Best Case: O(n)
- When the pattern is found at the very beginning of the text (or very early on).
- The algorithm will perform a constant number of comparisons, typically on the order of O(n) comparisons, where n is the length of the pattern.
Worst Case: O(n2)
- When the pattern doesn’t appear in the text at all or appears only at the very end.
- The algorithm will perform O((n-m+1)*m) comparisons, where n is the length of the text and m is the length of the pattern.
- In the worst case, for each position in the text, the algorithm may need to compare the entire pattern against the text.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...