Функция отказа KMP

Question

Я недавно изучил алгоритм сопоставления строк KMP, и я почти все это получил.Но я не понимаю, как построить функцию отказа в O ( length_of_pattern ).Мне не нужен код, мне нужно четкое объяснение, если это возможно.Заранее спасибо!

Answer 1

из этого сайта :

Алгоритм KMP предварительно обрабатывает шаблон P путем вычисления функции отказа f, которая указывает максимально возможный сдвиг s ​​с использованием ранее выполненных сравнений.

В частности, функция отказа f (j) определяется как длина самого длинного префикса P, который является суффиксом P [i.,j].

Вот псевдокод для строительства, я думаю, вы можете получить подробное объяснение на сайте

        KNUTH-MORRIS-PRATT FAILURE (P)

            Input:    Pattern with m characters
            Output: Failure function f for P[i . . j]

            i ← 1
            j ← 0
            f(0) ← 0
            while i < m do    /// your complexity will be O(length of pattern)
                if P[j] = P[i]
                    f(i) ← j +1
                     i ← i +1
                      j← j + 1
                else if (j != 0)
                     j ← f(j - 1)
                else
                    f(i) ← 0
                    i ← i +1

Надеюсь, что это ответит на вашвопрос