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).
As we can see,the pattern in the example occurs in the string.
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*/
The above algorithm can be optimized using the following technique:
When all characters of the pattern are different:
If after ‘k’ elements have been matched a mismatch occurs,
We can shift the pattern by ‘k’ instead of 1.
“ 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.