Что такое logi c за массивом lps [] в алгоритме KMP?

Question

Меня особенно смущает, как массив lps [] на самом деле захватывает то, что ему нужно, т.е. при каждом индексе, как он на самом деле захватывает самый длинный правильный префикс, равный суффиксу. Я dry запускаю код для массива lps [] для ввода «axabaxababa», и мне особенно важно, почему, когда pattern [i] не равен pattern [len] и len! = 0, почему, во имя Бога, Len = LPS [LEN-1]; Вот код для справки.

    len=0;
    lps[0]=0;
    for(int i=1;i<pattern.length();i++)
    {
        if(pattern[i]==pattern[len])
        {
          len++;
          lps[i]=len;  
        }
        else
        {
          if(len==0)
          {
              lps[i]=0;
          }
          else
          {
             len=lps[len-1];
              i--; 
          }   
        }    
    }