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 MN
2
MN and MN
MN and MN
2
Submit
What state is the DFA below in after simulating it on the input string ABCAABABABAB?
0
2
4
None of these
Submit
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
Submit