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

A. O(m*n)

B. O(m log n)

C. O(n)

D. O(m + n)

A. Boyer-Moore

B. Knuth-Morris-Pratt (KMP)

C. Rabin-Karp

D. Naive Search

A. It preprocesses the text.

B. It creates hash values for substrings.

C. It processes the text in reverse.

D. It shifts the pattern to align with previously matched suffixes.

A. Boyer-Moore

B. Knuth-Morris-Pratt (KMP)

C. Rabin-Karp

D. Naive Search

A. It uses advanced hashing techniques.

B. It requires sorting the pattern.

C. It is simple to implement.

D. It has a high worst-case time complexity.

A. Theta(m²)

B. Theta(mlogn)

C. Theta(m)

D. Big-Oh(n)

A. 13

B. 14

C. 12

D. 11

A. Hashing

B. Sorting

C. Augmenting

D. Dynamic Programming

A. O(n)

B. O(log n)

C. O(m+n)

D. O(mn)

A.

for s=0 to n
    do if p=t0	
        then if P[1..m]=T[s+1..s+m]
	    then print “Pattern occurs with shift” s

B.

for s=0 to n-m
    do if p=ts	
        then if P[1..m]=T[s+1..s+m]
	    then print “Pattern occurs with shift” s

C.

for s=0 to m
    do if p=ts	
        then if P[1..m]=T[s+1..s+m]
            then print “Pattern occurs with shift” s

D.

for s=0 to n-m
    do if p!=ts	
        then if P[1..m]=T[s+1..s+m]
	    then print “Pattern occurs with shift” s