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).
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Implement Bubble Sort using C.
What are the methodology for dialog design?
Explain the LOC, Function point and Feature point?
Create a Sparse Matrix in C.
Define packet switching and circuit switching. What is MANET?
Write short notes: B tree
Discuss about Staffing
