Automate finite si KMP

[•stef2n]

Comentarii la articolul Automate finite si KMP

[•cristiprg]

Cod:

daca q apartine A
          scrie "potrivire la pozitia " i - n + 1

nu ar trebui sa fie n - i + 1? 

[•Prostu]

Cod:

daca q apartine A
          scrie "potrivire la pozitia " i - n + 1

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.

[•alexandru92]

k = 2; δ(1, a) = 3;

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

[•APOCALYPTO]

k = 2; δ(1, a) = 3;

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.

[•ionutz32]

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.

[•APOCALYPTO]

Excelenta explicatie.
Multumesc mult Ionut!

[•PlayLikeNeverB4]

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.

[•VisuianMihai]

    Q = {q0, q1, q2, q3}
    A = {q3}
    Σ = {a, b}
    δ =

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

[•pauldb]

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).

[•witsel]

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.