Users Online

· Guests Online: 108

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads
No Threads created
Hottest Threads
No Threads created

Latest Articles

C++ Program to Find the Median of Two Sorted Arrays using Divide and Conquer

C++ Program to Find the Median of Two Sorted Arrays using Divide and Conquer

 

 

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

 

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.

No Ratings have been Posted.
Render time: 1.07 seconds
10,258,905 unique visits