h3. Algoritm_potrivire_cu_automat_finit

== code(c) | n = lungime(N)

== code(c) |
n = lungime(N)

q = 0;
pt i <- 1, n
    q = d(q, M[i])

* Complexitate : $O(n)$

Sa vedem cum se construieste automatul de potrivire pentru un string N. Fie m = lungime(M). Construim un automat cu m + 1 stari {q0, q1, ... qm}, A = {qm} . Faptul ca ne aflam in starea x inseamna ca au fost acceptate primele x caractere din sirul de intrare.
Din fiecare stare qx apartine Q si pt fiecare c apartine S construim d(x, c) = y cu proprietatea ca My este cel mai lung prefix al lui M care este sufix al lui Mxc (prefixul de lungime x al lui M, concatenat cu caracterul c).

Sa vedem cum se construieste automatul de potrivire pentru un string {$N$}. Fie {$m = lungime(M)$}. Construim un automat cu $m + 1$ stari {{$q{~0~}, q{~1~}, ... q{~m~}$}}, $A = {q{~m~}}$ . Faptul ca ne aflam in starea $x$ inseamna ca au fost acceptate primele $x$ caractere din sirul de intrare.
Din fiecare stare $q{~x~}$ apartine $Q$ si pt fiecare $c$ apartine $S$ construim $δ(x, c) = y$ cu proprietatea ca $M{~y~}$ este cel mai lung prefix al lui $M$ care este sufix al lui $M{~x~}c$ (prefixul de lungime $x$ al lui {$M$}, concatenat cu caracterul {$c$}).

h3. Algoritm_constructie_automat_finit

1: m <- lungime(M)
2: pt q <- 0, m
3: pt c apartine S
4: gaseste Mi = cel mai lung prefix al lui M cu Mi sufix al lui Mqc
5: d(q, c) = i

== code(c) |
m <- lungime(M)
pt q <- 0, m
    pt c apartine S
        gaseste M[i] = cel mai lung prefix al lui M cu M[i] sufix al lui M[q]c
&#0948;(q, c) = i
==

complexitate : linia 4 are complexitatea O(m^2) (implementata in maniera bruta) si se executa de (m + 1) * |S| ori => complexitate totala O(m^3 * |S|)