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
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
What is “Top-Down and Bottom-Up Design” approach?
What is an unrolled linked list?
Short Notes :Lines of Code (LOC)
Describe Cost of Software Quality
What are the propositions of Putnam’s model?
Discuss the ACID properties of transaction.
Write short notes on the following :
a) BFS
b) Tail recursion
