отказ функции КМП

Question

У меня есть вопрос о функции отказа KMP f. Предположим, что размер шаблона равен 2 ^ q, где q больше или равно 8.

Как я могу найти значения f (m / 2) и f (3m / 4), если я знаю, что f (m / 4) = 0 и f (m) = 3m / 4 заранее?

Какой стратегии я должен следовать? Я думаю, что я получаю алгоритм KMP более или менее, но я не могу найти способ думать здесь. Любые советы приветствуются.

Answer 1

Мы знаем, что f (m) = 3m / 4. Таким образом, необходимо, чтобы f (i) с i, принадлежащим {m / 4; m}, было равно i-m / 4 (все натуральные числа от 0 до 3m / 4). Так что в этом случае, f (m / 2) = m / 4 (потому что m / 4 = m / 2-m / 4) и f (3m / 4) = m / 2 (потому что m / 2 = 3m / 4- м / 4)