Searching for Patterns | Set 4 (A Naive Pattern Searching Question) | GeeksforGeeks

Consider a situation where all characters of pattern are different. Can we modify the original Naive String Matching algorithm so that it works better for these types of patterns.

When a mismatch occurs after j matches, we know that the first character of pattern will not match the j matched characters because all characters of pattern are different. So we can always slide the pattern by j without missing any valid shifts.

void search(char *pat, char *txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

    int i = 0;

 

    while(i <= N - M)

    {

        int j;

 

        /* For current index i, check for pattern match */

        for (j = 0; j < M; j++)

        {

            if (txt[i+j] != pat[j])

                break;

        }

        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]

        {

           printf("Pattern found at index %d \n", i);

           i = i + M;

        }

        else if (j == 0)

        {

           i = i + 1;

        }

        else

        {

           i = i + j; // slide the pattern by j

        }

    }

}

Read full article from Searching for Patterns | Set 4 (A Naive Pattern Searching Question) | GeeksforGeeks