Description: Let the length of the pattern P be ‘m’. Consider a string S of length ‘n’, given m<n. We have to check if the pattern P occurs in the String S using Naive string matching algorithm(optimized version).

 
If video does not load, Click here
 
Example:

String:   “ipupilrocks”

Pattern: “rock”

As we can see,the pattern in the example occurs in the string.

Algorithm:

Consider the following code snippet:

for i=0 to n-m

{

            if(P[0…m-1]==S[i…i+(m-1)])/*compare the string and pattern*/

            PATTERN MATCHED;

}

The above algorithm can be optimized using the following technique:

When all characters of the pattern are different:

MODIFICATION:

If  after ‘k’ elements have been matched a mismatch occurs,

We can shift the pattern by ‘k’ instead of 1.

Eg:

    “ a l g o r o r x m ”

              “o r x”

“or” has been matched in both string and pattern.  Mismatch occur in the 3rd character of the pattern.

Here, the pattern can be shifted by 2 instead of 1, as “or” have been matched in both String and pattern.

 

Note that the above modification is applicable only when all characters in the pattern are different.

 Time Complexity:

O(n*m)

Go to top