Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Knuth,Moris and Pratt algorithm scan the text array T[1……n] to find that whether a pattern array P[1………..n] appears in the text array by using the auxiliary function П which is called the prefix function.
Compute_Prefix_Function(P)
m=length(P)
П[i]=0
K=0
For q=2 to m
{
While k>0 and P[k+1] != P[q]
{
K= П[k]
}
If P[k+1]=P[q]
Then k=k+1
П[q]=k
}
Return П
}
KMP_Matcher(T,P)
{
n=length(T)
m=length(P)
П= Compute_Prefix_Function(P)
For i=1to n
{
While q>0 and P[q+1]!=T[i]
q=П[q]
if P[q+1]=T[i]
q=q+1
}
If q=m
Print “pattern occurs with shift” i-m
q=П[q]
}
Time complexity analysis:
The for loop in the Compute_Prefix_Function(P) executes for m-1 times, so the complexity of Compute_Prefix_Function(P) is O(m) and the for loop on the KMP_Matcher algorithm runs for n times,so the complexity is O(n). As there is a call to function in Compute_Prefix_Function(P) in KMP_Mathcher, therefore the total time complexity of this algorithm is O(m+n).
Write short notes on
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Explain the LOC, Function point and Feature point?
Discuss about SCHEDULING
Write a C program to multiplication of two matrix.
Why Required of ISO 9001:2000 standard?