Knuth Morris Pratt Algorithm in C++

This C++ program implements the Kunth-Morris-Pratt Algorithm for string matching. A text and a pattern is given as input. The pattern is searched for in the text and all instances of the pattern are given as output.

This C++ program is successfully compiled and run on Code::Blocks 10.05, a C++ compiler. The program output is given below.

```
 
```
```
#include<stdio.h>
```
```
#include<string.h>
```
```
#include<stdlib.h>
```
```
 
```

void computeLPSArray(char *pat, int M, int *lps);

```
 
```
```
void KMPSearch(char *pat, char *txt)
```
```
{
```
```
    int M = strlen(pat);
```
```
    int N = strlen(txt);
```
```
 
```

    // create lps[] that will hold the longest prefix suffix values for pattern

    int *lps = (int *)malloc(sizeof(int)*M);

```
    int j  = 0;  // index for pat[]
```
```
 
```

    // Preprocess the pattern (calculate lps[] array)

```
    computeLPSArray(pat, M, lps);
```
```
 
```
```
    int i = 0;  // index for txt[]
```
```
    while(i < N)
```
```
    {
```
```
      if(pat[j] == txt[i])
```
```
      {
```
```
        j++;
```
```
        i++;
```
```
      }
```
```
 
```
```
      if (j == M)
```
```
      {
```

        printf("Found pattern at index %d \n", i-j);

```
        j = lps[j-1];
```
```
      }
```
```
 
```
```
      // mismatch after j matches
```
```
      else if(pat[j] != txt[i])
```
```
      {
```

        // Do not match lps[0..lps[j-1]] characters,

```
        // they will match anyway
```
```
        if(j != 0)
```
```
         j = lps[j-1];
```
```
        else
```
```
         i = i+1;
```
```
      }
```
```
    }
```
```
    free(lps); // to avoid memory leak
```
```
}
```
```
 
```

void computeLPSArray(char *pat, int M, int *lps)

```
{
```

    int len = 0;  // lenght of the previous longest prefix suffix

```
    int i;
```
```
 
```
```
    lps[0] = 0; // lps[0] is always 0
```
```
    i = 1;
```
```
 
```

    // the loop calculates lps[i] for i = 1 to M-1

```
    while(i < M)
```
```
    {
```
```
       if(pat[i] == pat[len])
```
```
       {
```
```
         len++;
```
```
         lps[i] = len;
```
```
         i++;
```
```
       }
```
```
       else // (pat[i] != pat[len])
```
```
       {
```
```
         if( len != 0 )
```
```
         {
```

           // This is tricky. Consider the example AAACAAAA and i = 7.

```
           len = lps[len-1];
```
```
 
```

           // Also, note that we do not increment i here

```
         }
```
```
         else // if (len == 0)
```
```
         {
```
```
           lps[i] = 0;
```
```
           i++;
```
```
         }
```
```
       }
```
```
    }
```
```
}
```
```
 
```

// Driver program to test above function

```
int main()
```
```
{
```
```
   char *txt = "ABABDABACDABABCABAB";
```
```
   char *pat = "ABABCABAB";
```
```
   KMPSearch(pat, txt);
```
```
   return 0;
```
```
}
```

 
Output
 
Found pattern at index 10

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Perform String Matching using Vectors

» Next - C++ Program to Implement Rabin-Karp Method for Pattern Searching

Related Posts:

Recommended Articles: