Perform an experimental comparison of the rleative speeds of the KMP patter nmat
ID: 3605184 • Letter: P
Question
Perform an experimental comparison of the rleative speeds of the KMP patter nmatching algorithm.
Implement the KMP Fail function below and test it on a small, medium, and large text document. Documenting the run time for each test.
The Knuth-Morris-Pratt (KMP) Algorithms: 1 def compute.kmp.fail(P) 2 Utility that computes and returns KMP 'fail list." 4 fail = [0] * m 6k=0 m = len(P) # by default, presume overlap of 0 everywhere # compute f(j) during this pass, if nonzero # k + 1 characters match thus far 7 while j 0: # k follows a matching prefix else # no match found starting at JExplanation / Answer
#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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.