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