Какова функция алгоритма отказов KMP?

Question

Каковы надлежащие функции, которые говорят нам таблицу отказа KMP?

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

Считаю, что мы начинаем с -1 и 0, но я не могу понять остальную часть таблицы.

Answer 1

Вы можете посмотреть алгоритм aho-corasick, и функция сбоя вычисляется с помощью обхода ширины trie. Вы проходите каждый уровень и каждый ребенок сначала с очередью.