Naive Pattern Searching algorithm
Naive pattern searching is the simplest method among other pattern-searching algorithms. It checks for all characters of the main string to the pattern. This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find the substring by checking once for the string. It also does not occupy extra space to perform the operation.
Compare text characters with pattern characters
The time complexity of Naive Pattern Search method is O(m*n). The m is the size of pattern and n is the size of the main string.
C++
// C++ program for Naive Pattern // Searching algorithm #include <bits/stdc++.h> using namespace std; void search(char* pat, char* txt) { int M = strlen(pat); int N = strlen(txt); /* A loop to slide pat[] one by one */ for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break; if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] cout << "Pattern found at index " << i << endl; } } // Driver's Code int main() { char txt[] = "AABAACAADAABAAABAA"; char pat[] = "AABA"; // Function call search(pat, txt); return 0; } |
Java
// Java program for Naive Pattern // Searching algorithm class GFG { static void search(char[] pat, char[] txt) { int M = pat.length; int N = txt.length; /* A loop to slide pat[] one by one */ for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break; // if pat[0...M-1] = txt[i, i+1, ...i+M-1] if (j == M) System.out.println("Pattern found at index " + i); } } // Driver's Code public static void main(String[] args) { char txt[] = "AABAACAADAABAAABAA".toCharArray(); char pat[] = "AABA".toCharArray(); // Function call search(pat, txt); } } // This code is contributed by karandeep1234 |
Python3
# Python program for above approach def search(pat, txt): M = len(pat) N = len(txt) for i in range(N-M): for j in range(M): k = j+1 if(txt[i+j] != pat[j]): break if(k == M): print("Pattern found at index ", i) txt = "AABAACAADAABAAABAA"pat = "AABA"search(pat, txt) # This code is contributed by ishankhandelwals. |
C#
using System; public class GFG { public static void search(char[] pat, char[] txt) { int M = pat.Length; int N = txt.Length; /* A loop to slide pat[] one by one */ for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break; if (j == M) // if pat[0...M-1] = txt[i, i+1, // ...i+M-1] Console.WriteLine("Pattern found at index " + i); } } static public void Main() { char[] txt = "AABAACAADAABAAABAA".ToCharArray(); char[] pat = "AABA".ToCharArray(); // Function call search(pat, txt); } } // This code is contributed by akashish__ |
Javascript
// JS program for Naive Pattern // Searching algorithm function search(pat, txt) { let M = pat.length; let N = txt.length; /* A loop to slide pat[] one by one */ for (let i = 0; i <= N - M; i++) { let j = 0; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break; if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] console.log("Pattern found at index",i); } } // Driver's Code let txt = "AABAACAADAABAAABAA"; let pat = "AABA"; // Function call search(pat, txt); // This code is contributed by ishankhandelwals. |
Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Introduction to Pattern Searching – Data Structure and Algorithm Tutorial
Pattern searching is an algorithm that involves searching for patterns such as strings, words, images, etc.
We use certain algorithms to do the search process. The complexity of pattern searching varies from algorithm to algorithm. They are very useful when performing a search in a database. The Pattern Searching algorithm is useful for finding patterns in substrings of larger strings. This process can be accomplished using a variety of algorithms that we are going to discuss in this blog.
Introduction to Pattern Searching – Data Structure and Algorithm Tutorial
Contact Us