Naive Pattern Searching

In this tutorial we will learn to search pattern in a given string using naive approach.

About naive approach

We are given a string of characters and a pattern the mission is to search for the pattern in the given string.

In the naive approach we match the pattern with the string at every position.

Note! the length of the pattern (no. of characters) will be smaller than or equal to the length of the string

If the length of the pattern is greater
than the string then we can easily say “Pattern Not Found!”

Problem

Consider the following string and pattern.

Where, pLen = 2 is the length (no. of characters) of pattern p. And strLen = 7 is the length of the string str.

Mission

Our mission is to find the positions where the pattern p is found in the given string str.

Steps

In the naive approach we use the following steps.

Set Limit = strLen - pLen
for ( i = 0; i <= Limit; i++ ) {
    for ( j = 0; j < pLen; j++ ) {
        if ( p[ j ] != str[ i + j ] )
            break
    }
    if ( j == pLen )
        Print: "Pattern found at position " + i
}

Positions where pattern p is found

    +---+---+---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | <-- array index
    +---+---+---+---+---+---+---+
str | A | A | B | A | A | A | B | <-- characters
    +---+---+---+---+---+---+---+
    <---p--->   <---p--->
                    <---p--->

Code in C

#include <stdio.h>
#include <string.h>

void searchPatter_novice(char *str, char *p);

void searchPatter_novice(char *str, char *p) {

  /**
   * length of the string and pattern
   */
  int pLen = strlen(p);
  int strLen = strlen(str);

  /**
   * variables
   */
  int Limit, i, j;

  Limit = strLen - pLen;

  for (i = 0; i <= Limit; i++) {
    for (j = 0; j < pLen; j++) {
      if(p[j] != str[i+j]) {
        break;
      }
    }
    if(j == pLen) {
      printf("Pattern found at position %d\n", i);
    }
  }
}

int main(void) {

  //the string
  char str[] = "AABAAAB";

  //pattern to search
  char p[] = "AA";

  //search for pattern
  searchPatter_novice(str, p);

  return 0;
}

Output

Pattern found at position 0
Pattern found at position 3
Pattern found at position 4

Time complexity

Time complexity is O(pLen x (1 + strLen - pLen) ) i.e., O(strLen x pLen) where strLen and pLen are the length of the string and the pattern respectively.