Question:

Published on: 29 May, 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 : 579

29 May, 2024

**Write short notes on**

**Kruskal’s algorithm for finding MST****Graph coloring problem**

View : 487

29 May, 2024

Random questions

29 May, 2024

29 May, 2024

**Describe Dimension of Software Quality**

30 May, 2022

**What is SRS? Write the features of SRS.**

29 May, 2024

**Write a C program to convert any number into word.**

29 May, 2024