KMP iZ algorytmy są dobrze znanymi algorytmami wyszukiwania łańcuchów,

KMP algorytm zajmuje się znajdowaniem wzorców poprzez funkcję awarii KMP, która jest zdefiniowana jako (pat będący wzorem wyszukiwania)

lps [i] = najdłuższy właściwy przedrostek pat [0..i], który jest również przyrostkiem pat [0..i].

npstring "abcab" to byłby[0, 0, 0, 1, 2]

natomiastZ algorytm używa funkcji z, która jest zdefiniowana jako:

Biorąc pod uwagę łańcuch S o długości n, algorytm Z tworzy tablicę Z, gdzie Z [i] jest długością najdłuższego podciągu zaczynającego się od pat [i], który jest również przedrostkiem pat.

Teraz pytanie brzmi: czy możemy osiągnąćZ funkcja za pomocąKMP algorytm? To, czego szukam, to pewne modyfikacje wlps tablica, która prowadzi do tych samych wyników coZ[i] szyk.