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 10Input: 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++
// C++ program for Naive Pattern// Searching algorithm#include <bits/stdc++.h>using namespace std;void search(string& pat, string txt){ int M = pat.size(); int N = txt.size(); /* 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 Codeint main(){ string txt = "AABAACAADAABAAABAA"; string pat = "AABA"; // Function call search(pat, txt); return 0;}// This code is contributed// by Akanksha Rai |
C
// C program for Naive Pattern Searching algorithm#include <stdio.h>#include <string.h>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] printf("Pattern found at index %d \n", i); }}// Driver's codeint main(){ char txt[] = "AABAACAADAABAAABAA"; char pat[] = "AABA"; // Function call search(pat, txt); return 0;} |
Java
// Java program for Naive Pattern Searchingpublic 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++; } } // Driver's code public static void main(String args[]) { String pat = "AABAACAADAABAAABAA"; String txt = "AABA"; // Function call search(pat, txt); }}// This code is contributed by D. Vishnu Rahul Varma |
Python3
# Python3 program for Naive Pattern# Searching algorithmdef search(pat, txt): M = len(pat) N = len(txt) # A loop to slide pat[] one by one */ for i in range(N - M + 1): j = 0 # For current index i, check # for pattern match */ while(j < M): if (txt[i + j] != pat[j]): break j += 1 if (j == M): print("Pattern found at index ", i)# Driver's Codeif __name__ == '__main__': txt = "AABAACAADAABAAABAA" pat = "AABA" # Function call search(pat, txt)# This code is contributed# by PrinciRaj1992 |
C#
// C# program for Naive Pattern Searchingusing System;class GFG { public static void search(String txt, String pat) { 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) Console.WriteLine("Pattern found at index " + i); } } // Driver's code public static void Main() { String txt = "AABAACAADAABAAABAA"; String pat = "AABA"; // Function call search(txt, pat); }}// This code is Contributed by Sam007 |
Javascript
// Javascript program for Naive Pattern Searchingfunction search(txt, pat){ 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; /* 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) document.write("Pattern found at index " + i + "</br>"); }}let txt = "AABAACAADAABAAABAA";let pat = "AABA";search(txt, pat); |
PHP
<?php// PHP program for Naive Pattern// Searching algorithmfunction search($pat, $txt){ $M = strlen($pat); $N = strlen($txt); // A loop to slide pat[] // one by one for ($i = 0; $i <= $N - $M; $i++) { // 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) echo "Pattern found at index ", $i."\n"; }} // Driver Code $txt = "AABAACAADAABAAABAA"; $pat = "AABA"; search($pat, $txt); // This code is contributed by Sam007?> |
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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
