String Matching MCQ question and answer with solution | Data Structure MCQs

Home / Data Structure / String Matching

52.
If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable modulus to reduce the complexity)
p=0; t0=0;

for i=1 to n
do t0=(dt0 + P[i])mod q 
p=(dp+T[i])mod q

for i=1 to n
do p=(dp + P[i])mod q 
t0=(dt0+T[i])mod q

for i=1 to m
do t0=(dp + P[i])mod q 
p=(dt0+T[i])mod q

for i=1 to m
do p=(dp + P[i])mod q 
t0=(dt0+T[i])mod q

Answer & Solution Discuss in Board Save for Later

58.
If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin Karp Algorithm?

Answer & Solution Discuss in Board Save for Later

59.
Which of the following algorithms formed the basis for the Quick search algorithm?

Answer & Solution Discuss in Board Save for Later

60.
Given a pattern of length- 5 window, find the valid match in the given text.
Pattern: 2 1 9 3 6 
Modulus: 21
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Text:   9 2 7 2 1 8 3 0 5 7 1   2   1   2   1   9   3   6   2   3   9  7

Answer & Solution Discuss in Board Save for Later