Объяснения о свойстве функции отказа KMP

Question

Я читал topcoder tutorial on KMP algorithm, и я не в состоянии понять следующую часть текста:

Учитывая строку (довольно длинный), найти все свои собственные суффиксы, также являются префиксами. Все, что нам нужно сделать, это просто вычислить «отказ» функции данной строки и использовать в ней информацию , чтобы распечатать ответ.

Я знаю, как вычислить функцию отказа и для строки abacababa я получаю следующий массив [0, 0, 1, 0, 1, 2, 3, 2, 3]. Проблема заключается в том, что я не могу понять, как это может помочь мне найти

все свои собственные суффиксы, которые также являются префиксы него

, которые основаны на моем понимании, предполагают, чтобы быть a и aba.

Answer 1

Самый длинный собственный суффикс, который также является префиксом, является префиксом длины p[n - 1]. Следующий - самый длинный суффикс этого суффикса, который также является префиксом. Это точно префикс длины p[p[n - 1] - 1]. Мы продолжаем повторять его, пока не получим пустой префикс.

Например, для этой abacaba строки она идет так:

1. Самый длинный собственный суффикс, который также является префиксом aba (потому что p[n - 1] является 3).

2. Самый длинный собственный суффикс, который также является префиксом aba является a (потому что это p[2]1).

3. Нет такого суффикса для a (p[0] = 0), поэтому мы закончили.

код выглядит следующим образом:

cur = p[n - 1] 
while cur != 0: 
    print(s[0 ... cur - 1]) 
    cur = p[cur - 1]