KMP

Z RNO-Wiki

Automaty skończone

Wyszukiwanie wzorca w tekście można realizować za pomocą pewnych automatów skończonych. Oto przykład automatu rozpoznającego w tekscie wzorzec "abaaba" :

Abaaba.gif

Funkcja prefiksowa Knutha

Dla słowa P[1..n] definiujemy funkcję prefiksową Knutha następująco:

pi[k] = długość najdłuższego prefiksu słowa P[1..(k-1)] będącego sufiksem słowa P[1..k]

Ciąg dalszy nastąpi. Na razie zamieszczam link do notatek z Wikipedii [1].

Osobiste