Расчет функции отказа КМП

Question

Мой профессор решил функцию отказа KMP следующим образом:

index  1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff     0 1 2 1 2 3 4 5 1

Из других текстов, которые я проверил онлайн, я обнаружил, что это может быть неправильно, я вернулся, чтобы подтвердить от него снова, и он сказал мне, что он абсолютно прав. Может кто-нибудь, пожалуйста, объясните мне, почему он думает, что это правильно или неправильно в простой пошаговой манере? Спасибо

Answer 1

Как я понимаю алгоритм, функция сбоя для вашего примера должна быть следующей:

1 2 3 4 5 6 7 8 9
aabaababb

0 1 0 1 2 3 4 0 0

f - функция сбоя (по определению это длина самого длинного префикса строки, который также является суффиксом)

Вот как я построил это шаг за шагом:

f (a) = 0 (всегда = 0 для одной буквы)

f (aa) = 1 (одна буква "a" является префиксом и суффиксом)

f (aab) = 0 (нет одинаковых суффиксов и префиксов: a! = b, aa! = ab)

f (aaba) = 1 ("a" одинаково в начале и в конце, но если взять 2 буквы, они не будут равны: aa! = ba)

f (aabaa) = 2 (вы можете взять 'aa', но не более: aab! = baa)

f (aabaab) = 3 (вы можете взять 'aab')

f (aabaaba) = 4 (вы можете взять 'aaba')

f (aabaabab) = 0 ('a'! = 'b', 'aa'! = 'ab' и т. д., не может быть = 5, так как 'aabaa'! = 'aabab')

f (aabaababb) = 0 (та же ситуация)

Answer 2

Поскольку @user1041889 был сбит с толку (и меня тоже смутил), я приведу здесь различия между Z-функцией и функцией отказа.

Функция отказа, π[i]:

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

Но это, возможно, китайский язык, поэтому я умолчу, чтобы действительно понять, что я говорю:

Насколько велика самая длинная подстрока в начале интересующей строки, равная подстроке, заканчивающейся индексом

Или эквивалентно:

Какова длина самой большой подстроки, заканчивающейся индексом iкоторый соответствует началу интересующей строки

Итак, в вашем примере:

      index  1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff     0 1 0 1 2 3 4 0 0

Мы наблюдаем, что π[6] = 3, так что же это за подстрока, оканчивающаяся на индекс 6 и имеющая длину 3? aab!

Интересно, как мы видели это раньше!

Проверим, что он действительно самый большой: baab != aab. Ага!

Обратите внимание, как это означает, что функции отказов всегда растут равномерно.

Это не относится к Z-алгоритму.

[СОХРАНЕНИЕ ЧЕРНОВИКА, чтобы продолжить позже]