infoarena

Comentarii la articolul Automate finite si KMP (http://infoarena.ro/automate-finite-si-kmp)

nu ar trebui sa fie n - i + 1?  :?

Nu acolo este problema. Iteratorul 'i' trebuie sa il parcurga pe M, deci bucla pentru este intre 1 si lungimea lui M.
Am modificat codul in mod corespunzator. Multumim pentru observatie.

k n-ar trebui sa fie 1, sau ... ?

Cred ca ai dreptate.

Imi poate explica si mie cineva care stie bine ideea din spatele algoritmului KMP de ce
k <- pi[k] (linia 6 la functia prefix si linia 5 la functia KMP)?
Adica vreau sa stiu de ce functioneaza.

Pai, sa zicem ca avem un sir pe care il parcurgem pentru a afla functia pi.
Cand suntem la pozitia i, prefixul parcurs pana acum va fi ceva de genul:

abacabadabacaba

Cand trecem la pozitia i+1, se mai adauga un caracter.
pi[i] (zis si k) indica sirul "abacaba" (cel mai lung prefix care e si sufix). Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'd'. Daca se potriveste, inseamna ca pi[i+1] <- k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

abacaba

pi[k] indica sirul "aba", iar k va primi valoarea lui pi[k] si se repeta pasii. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'c'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

aba

pi[k] indica sirul "a", iar k <- pi[k]. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'b'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

a

pi[k]=0, se va face o ultima verificare si daca nici de data asta nu coincide, pi[i+1] va fi 0.
Ideea e ca pe masura ce ne indreptam in sir spre stanga, prefixul de lungime k e acelasi cu sufixul de lungime k, in continuarea caruia trebuie pus caracterul de pe poz i+1.
Pe aceeasi idee se bazeaza si codul Algoritm_potrivire_KMP.

Excelenta explicatie.
Multumesc mult Ionut!

Bun articol. Am reusit sa inteleg dupa cateva ore de chinuiala. Pana la urma mi-am dat seama ca defapt algoritmul nu face decat sa caute in mod normal sirul N in M si verifica daca cumva exista mai multe potriviri care "se suprapun". Functia pi arata urmatorul loc unde e posibila aceasta suprapunere.

Asta vad eu pe ecran. Asa trebuie sa fie la functia de potrivire δ ? Daca nu, imi puteti spune valoarea care lipseste?

Functia delta este data de tabelul de mai jos. Prima coloana reprezinta nodul sursa, iar ultimele doua reprezinta nodurile destinatie in functie de caracterul citit (a sau b).

vectorul pi reprezinta starile automatului, iar cu q doar parcurgem starile sau cum este?? ca nu am inteles foarte bine de ce nu scade q cu 1 ci se foloseste
while (q && A[q+1] != A)
            q = pi[q];
Adica am observat pe niste exemple ca asa este dar as vrea sa-mi explice cineva concret DE CE este asa.