Funkcja awarii KMP - ciąg, algorytm, funkcja, wydajność, dopasowywanie wzorców

Niedawno nauczyłem się algorytmu dopasowywania ciągów KMP, i prawie dostaję to wszystko.Ale nie dostaję, jak zbudować funkcję awarii w O ( length_of_pattern ). ja don "t potrzebujesz kodu, potrzebuję jasnego wyjaśnienia, jeśli to możliwe. Z góry dziękuję!

Odpowiedzi:

od ta strona:

Algorytm KMP wstępnie przetwarza wzorzec P, obliczając funkcję uszkodzenia f, która wskazuje największą możliwą zmianę s przy użyciu wcześniej wykonanych porównań.

W szczególności funkcja niepowodzenia f (j) jest zdefiniowana jako długość najdłuższego przedrostka P, który jest sufiksem P [i. . jot].

Oto pseudo kod do budowy, myślę, że możesz uzyskać szczegóły objaśnień na stronie

        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

Mam nadzieję, że odpowie na twoje pytanie