Naive Method

Posted By on November 5, 2014

Download PDF
Method for string matching
Finite Automaton Method

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

1) Input:

  txt[] =  "THIS IS A TEST TEXT"
  pat[] = "TEST"


Pattern found at index 10

2) Input:

  pat[] = "AABA"


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

Pattern searching is an important problem in computer science. When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results.

Naive Pattern Searching:
Slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches.

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])
        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
           printf("Pattern found at index %d n", i);
/* Driver program to test above function */
int main()
   char *txt = "AABAACAADAABAAABAA";
   char *pat = "AABA";
   search(pat, txt);
   return 0;

What is the best case?
The best case occurs when the first character of the pattern is not present in text at all.

txt[]  = "AABCCAADDEE"
pat[] = "FAA"

The number of comparisons in best case is O(n).

What is the worst case ?
The worst case of Naive Pattern Searching occurs in following scenarios.
1) When all characters of the text and pattern are same.

pat[] = "AAAAA".

2) Worst case also occurs when only the last character is different.

pat[] = "AAAAB"

Number of comparisons in worst case is O(m*(n-m+1)). Although strings which have repeated characters are not likely to appear in English text, they may well occur in other applications (for example, in binary texts). The KMP matching algorithm improves the worst case to O(n).

Method for string matching
Finite Automaton Method

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby