Почему KMP O (n + m)?
Я знаю, что этот вопрос, возможно, задавался здесь миллион раз, но я не нашел решения, которое убедило бы меня / меня поняли, или вопрос, которыйсоответствует моему примеру.
/**
* KMP algorithm of pattern matching.
*/
public boolean KMP(char []text, char []pattern){
int lps[] = computeTemporaryArray(pattern);
int i=0;
int j=0;
while(i < text.length && j < pattern.length){
if(text[i] == pattern[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j == pattern.length){
return true;
}
return false;
}
n = размер текстаm = размер шаблона
Я знаю, почему это + m, это время выполнения, необходимое для создания массива lsp для поиска.Я не уверен, почему код, который я передал выше, является O (n).
Я вижу, что выше "i" всегда прогрессирует вперед, ЗА ИСКЛЮЧЕНИЕМ, когда он не совпадает, и j! = 0. В этом случае,мы можем выполнять итерации цикла while, где я не двигаюсь вперед, поэтому он не совсем O (n)
Если массив lps увеличивается, как [1,2,3,4,5,6,0].Если мы не сможем найти совпадение с индексом 6, j обновится до 5, а затем до 4, а затем до 3 .... и т. Д., И мы фактически пройдем m дополнительных итераций (при условии, что все не совпадают).Это может происходить на каждом шагу.
, чтобы он выглядел как
for (int i = 0; i < n; i++) {
for (int j = i; j >=0; j--) {
}
}
, и для помещения всех возможных комбинаций ij, также называемых состояниями, потребуется массив m, поэтому время выполнения не будет равно O (n * 1018).* m).
Значит, мое чтение кода неверно, или неправильный анализ цикла for, или мой пример невозможен?