Users Online
· Guests Online: 108
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Newest Threads
No Threads created
Hottest Threads
No Threads created
Latest Articles
Articles Hierarchy
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.
-
/*
-
* C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)
-
*/
-
#include <iostream>
-
#include <cstring>
-
using namespace std;
-
void preKMP(string pattern, int f[])
-
{
-
int m = pattern.length(), k;
-
f[0] = -1;
-
for (int i = 1; i < m; i++)
-
{
-
k = f[i - 1];
-
while (k >= 0)
-
{
-
if (pattern[k] == pattern[i - 1])
-
break;
-
else
-
k = f[k];
-
}
-
f[i] = k + 1;
-
}
-
}
-
-
//check whether target string contains pattern
-
bool KMP(string pattern, string target)
-
{
-
int m = pattern.length();
-
int n = target.length();
-
int f[m];
-
preKMP(pattern, f);
-
int i = 0;
-
int k = 0;
-
while (i < n)
-
{
-
if (k == -1)
-
{
-
i++;
-
k = 0;
-
}
-
else if (target[i] == pattern[k])
-
{
-
i++;
-
k++;
-
if (k == m)
-
return 1;
-
}
-
else
-
k = f[k];
-
}
-
return 0;
-
}
-
-
int main()
-
{
-
string tar = "san and linux training";
-
string pat = "lin";
-
if (KMP(pat, tar))
-
cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
-
else
-
cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
-
pat = "sanfoundry";
-
if (KMP(pat, tar))
-
cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
-
else
-
cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
-
return 0;
-
}
$ 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.