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
function handleClick(group, correct_answer)
{
var amountCorrect = 0;
var radios = document.getElementsByName('group'+group);
for(var j = 0; j < radios.length; j++) {
var radio = radios[j];
if(radio.value == "correct" && radio.checked) {
amountCorrect++;
}
}
if (amountCorrect == 0)
alert("Incorrect. " + correct_answer);
else
alert("Correct!")
}
}