question is based on KMP algorithm and string matching algorithm: b) (5 marks) Given two strings, A

question is based on KMP algorithm and string matching algorithm:

 

Transcribed Image Text:

b) (5 marks) Given two strings, A = a1, a2,...am and B = b1, b2, ...bn, we define a matrix C[0..m, 0..n] as follows: (1 i m, 1 j n) C[0, 0] = 0, C[0, j] = j, C[i, 0] = i. - C[i, j] = min{C[i 1, j] + 1, C[i, j 1] + 1, C[i 1, j 1] + rij} where rij =1, if a bj. - - 0, if a = bj, or Compute the C matrix for strings A = ababab, and B = babaaa. What is the meaning of the value in C[m,n]? b) (5 marks) Given two strings, A = a1, a2,...am and B = b1, b2, ...bn, we define a matrix C[0..m, 0..n] as follows: (1 i m, 1 j n) C[0, 0] = 0, C[0, j] = j, C[i, 0] = i. - C[i, j] = min{C[i 1, j] + 1, C[i, j 1] + 1, C[i 1, j 1] + rij} where rij =1, if a bj. - - 0, if a = bj, or Compute the C matrix for strings A = ababab, and B = babaaa. What is the meaning of the value in C[m,n]?