string matching problem

Given a pattern P find all occurrence  of P in text T. For example if P = “aba ” and T = “bbabayababay’ ,then P occurs in T starting at positions 2, 6 and 8th index of  string T. look at the second occurrence at position 7 and third occurrence at position 9,This is called overlap of pattern P in text T.

Naive Pattern Searching solution

Let us discus a naive solution of string pattern searching or matching.

string matching z algorithm

From above figure we can say that string matching problem is a problem of finding all valid shifts of pattern p in given text T. The pattern P occurs in T starting at positions 3, 7 and 9.

Now let discuss a very efficient string matching Z algorithm , follow this link