KMP

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 05:42, 27 kwi 2007
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)

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