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).
Find the recurrence relation of binary search and derive the time complexity of binary search.
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
Write the characteristics of a good user interface.
What is Resource management?
Write a C program to check a number is even or odd.
Write a C program to find the GCD of two numbers.
