Naive pattern searching

Problem Statement: “Given a text and a pattern, write a program to print the occurrences of pattern in the text”

Examples:

Example 1:
Input: text[] = "BAABABAABBBABAA"
pat[] = "ABAA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
Explanation: Give a very clear understanding to the reader between the correlation of Input and Output relating to the problem statement.

Example 2:
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output:Pattern found at index 0
Pattern found at index 9
Pattern found at index 12

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

The idea is to search the whole array for the match, when the match is found print the starting index of the pattern in the text.

  • We are given an array of characters as text and pat.
  • Take two variables N and M representing the size of the text and pattern array.
  • Now use a for loop that takes elements one by one in a text array that runs till N. 
  • Inside the for loop check if there is an element match, then check for subsequent matches.
  • If a match is not present then break the inner loop and check for another element.
  • When all the elements in the pattern match, then print the ith index.
  • Since there are two loops one inside another, thus time complexity becomes O(N * M).


Code
:

C++ Code

#include <bits/stdc++.h>

using namespace std;

void search(char text[], char pat[]) {
  int N = strlen(text);
  int M = strlen(pat);

  // Check for each element in text
  for (int i = 0; i < N; i++) {
    int j;

    // Check whether all elements of pat are present in text, break if not found
    for (j = 0; j < M; j++)
      if (text[i + j] != pat[j])
        break;

    if (j == M) // When all element of pat are found, print ith index
      cout << "Pattern found at index " <<
      i << endl;
  }
}

// Driver Code
int main() {
  char text[] = "AABAACAADAABAAABAA";
  char pat[] = "AABA";
  search(text, pat);
  return 0;
}

Output:

Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Time Complexity: O(N * M)

Space Complexity: O(1)

Java Code

public class TUF {
  public static void search(String text, String pat) {
    int M = pat.length();
    int N = text.length();

    // Check for each element in text
    for (int i = 0; i < N - M; i++) {

      int j;

      //For current index i, check if pattern exist
      for (j = 0; j < M; j++)
        if (text.charAt(i + j) != pat.charAt(j))
          break;

      if (j == M) // When all element of pat are found, print ith index
        System.out.println("Pattern found at index " + i);
    }
  }
  public static void main(String args[]) {

    String text = "AABAACAADAABAAABAA";
    String pat = "AABA";
    search(text, pat);
  }
}

Output:

Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Time Complexity: O(N * M)

Space Complexity: O(1)

Special thanks to Rushikesh Aadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article