C++ Program to Implement KMP Pattern Searching Algorithm

«
»
This C++ Program demonstrates the implementation of Knuth–Morris–Pratt Algorithm popularly known as KMP.

Here is source code of the C++ Program to implement Knuth–Morris–Pratt Algorithm (KMP). The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)
  3.  */
  4. #include <iostream>
  5. #include <cstring>
  6. using namespace std;
  7. void preKMP(string pattern, int f[])
  8. {
  9.     int m = pattern.length(), k;
  10.     f[0] = -1;
  11.     for (int i = 1; i < m; i++)
  12.     {
  13.         k = f[i - 1];
  14.         while (k >= 0)
  15.         {
  16.             if (pattern[k] == pattern[i - 1])
  17.                 break;
  18.             else
  19.                 k = f[k];
  20.         }
  21.         f[i] = k + 1;
  22.     }
  23. }
  24.  
  25. //check whether target string contains pattern 
  26. bool KMP(string pattern, string target)
  27. {
  28.     int m = pattern.length();
  29.     int n = target.length();
  30.     int f[m];     
  31.     preKMP(pattern, f);     
  32.     int i = 0;
  33.     int k = 0;        
  34.     while (i < n)
  35.     {
  36.         if (k == -1)
  37.         {
  38.             i++;
  39.             k = 0;
  40.         }
  41.         else if (target[i] == pattern[k])
  42.         {
  43.             i++;
  44.             k++;
  45.             if (k == m)
  46.                 return 1;
  47.         }
  48.         else
  49.             k = f[k];
  50.     }
  51.     return 0;
  52. }
  53.  
  54. int main()
  55. {
  56.     string tar = "san and linux training";
  57.     string pat = "lin";
  58.     if (KMP(pat, tar))
  59.         cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
  60.     else
  61.         cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
  62.     pat = "sanfoundry";
  63.     if (KMP(pat, tar))
  64.         cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
  65.     else
  66.         cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
  67.     return 0;
  68. }

$ g++ kmp.cpp
$ a.out
 
'lin' found in string 'san and linux training'
'sanfoundry' not found in string 'san and linux training'
 
------------------
(program exited with code: 1)
Press return to continue

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.