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
Write a C program to convert binary to decimal using function.
What is Resource management?
Write a C program to transpose of a matrix.
