Почему самый длинный префикс, который также является частью вычисления суффикса в KMP, имеет временную сложность O (n), а не O (n ^ 2)?

Question

Я просматривал код KMP, когда заметил Longest Prefix, который также является частью вычисления суффикса KMP.Вот как это происходит,

void computeLPSArray(char* pat, int M, int* lps) 
{ 
    int len = 0; 

    lps[0] = 0;  

    int i = 1; 
    while (i < M) { 
       if (pat[i] == pat[len]) { 
          len++; 
          lps[i] = len; 
          i++; 
       } 
       else 
       { 
          if (len != 0) { 
              len = lps[len - 1]; //<----I am referring to this part

          } 
          else 
          { 
              lps[i] = 0; 
              i++; 
          } 
      } 
  } 
}

Теперь часть, в которой я запутался, была та, которую я показал в комментариях в приведенном выше коде.Теперь мы знаем, что когда код содержит цикл, подобный следующему

int a[m];
memset(a, 0, sizeof(a));
for(int i = 0; i<m; i++){
   for(int j = i; j>=0; j--){
       a[j] = a[j]*2;//This inner loop is causing the same cells in the 1 
                     //dimensional array to be visited more than once. 
   }
}

Сложность получается O (m * m).Точно так же, если мы запишем вышеупомянутое вычисление LPS в следующем формате

while(i<M){
   if{....}
   else{
      if(len != 0){
          //doesn't this part cause the code to again go back a few elements
          //in the LPS array the same way as the inner loop in my above 
          //written nested for loop does? Shouldn't that mean the same cell
          //in the array is getting visited more than once and hence the 
          //complexity should increase to O(M^2)?
      }
   }

}

Может случиться так, что способ, которым я думаю, что сложность вычислена, неправильный.Поэтому, пожалуйста, уточните.

Answer 1

Если вы тщательно проанализируете алгоритм создания таблицы префиксов, вы можете заметить, что общее количество откатных позиций может быть не более m, поэтому верхняя граница для общего числа итераций равна 2*m, что дает O(m)

Значение len растет вместе с основным итератором i, и при каждом несоответствии len возвращается к нулевому значению, но это "падение" не может превышать интервал, пройденный основным итератором i с начала матча.

Например, скажем, главный итератор i начал сопоставлять с len в позиции 5 и не совпал в позиции 20.
Итак,

LPS[5]=1  
LPS[6]=2  
...  
LPS[19]=15

В данный моментнесоответствия, len имеет значение 15. Следовательно, он может откатить максимум 15 позиций до нуля, что эквивалентно интервалу, пройденному i при сопоставлении.Другими словами, при каждом несоответствии len перемещается назад не более чем на i с момента начала матча

Answer 2

Если выражения не требуют времени, которое увеличивается с len.

Len - целое число.Чтение занимает O (1) раз.

Индексирование массива равно O (1).

Посещение чего-либо более одного раза не означает, что вы выше, O мудрый нотация.Только если число посещений растет быстрее, чем kn для некоторого k.