img
Question:
Published on: 29 March, 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).

 

Random questions