Как использовать функцию отказа KMP для определения минимальной длины повторной подстроки?

Question

Я хочу решить UVA 10298 -"Power Strings" проблема с использованием алгоритма KMP. В блоке this показано, как функция отказа может быть использована для вычисления минимальной длины подстроки. Этот метод выглядит следующим образом:

1. Вычислить префикс-суффикс-таблицу pi[ ] для данной строки.
2. Пусть len - длина строки, а last_in_pi - значение, хранящееся при последнем индексе таблицы pi.
3. Проверьте, соответствует ли len % (len - last_in_pi) == 0 или нет. Если это так, то длина повторяемой подстроки минимальной длины равна (len - last_in_pi), в противном случае это длина данной строки.

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

Answer 1

Помните, что Pi[i] определен как длинный префикс (длина) самого длинного префикса your_string, который является правильным суффиксом (а не всей строкой) подстроки your_string[0 ... i].

Существует пример на блоге вы связаны с:

0 1 2 3 4 5 
S : a b a b a b 
Pi: 0 0 1 2 3 4 

Где мы имеем:

б

абаб

И т.д. Надеюсь, это даёт понять, что такое Pi (префиксная функция/таблица).

Теперь, блог говорит:

Последнее значение префикса таблицы = 4 .. Теперь если это повторяется строка чем, это минимальная длина будет 2. (6 (длина строки) - 4),

Поэтому вы должны проверить, len % (len - last_in_pi) == 0. Если да, то len - last_in_pi - это длина кратчайшей повторяющейся строки (строка периода).

Это работает, потому что, если вы вращаете строку с len(period) позициями в любом случае, она будет соответствовать самой себе. len - last_in_pi расскажет вам, сколько вам нужно повернуть.