String Search quiz



Suppose that you want to count the number of all occurrences of some pattern string of length M in a text of length N. What is the order of growth of the best-case and worst-case running time of the brute-force algorithm? As usual, assume M≤ N.

N and MN
N and MN2
MN and MN
MN and MN2

What state is the DFA below in after simulating it on the input string ABCAABABABAB?

0
2
4
None of these

In the worst case, Knuth-Morris-Pratt substring search accesses how many characters to search for a pattern of length M in a text of length N?

M
N
M + N
MN