Question:

Published on: 12 October, 2024

**Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity. **

Answer:

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).

Subjects

Trending

**Find the recurrence relation of binary search and derive the time complexity of binary search.**

View : 979

12 October, 2024

**What do you mean by dynamic programming?** **Write the algorithm of chain matrix multiplication.**

View : 739

12 October, 2024

Random questions

**Write the characteristics of a good user interface.**

12 October, 2024

**What is Resource management?**

12 October, 2024

**Write a C program to check a number is even or odd.**

12 October, 2024

**Write a C program to find the GCD of two numbers.**

12 October, 2024

12 October, 2024