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

            d(q, c) = i

δ(q, c) = i

==

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

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

Practic, algoritmul calculeaza pentru toate {$0 ≤ i ≤ m$}, $c$ apartine $S$ cat de mult putem lua de la sfarsitul lui $M{~i~}c$ astfel incat acesta sa fie un "inceput" de {$N$}.

Practic, algoritmul calculeaza pentru toate 0 =< i =< m, c apartine S cat de mult putem lua de la sfarsitul lui Mic astfel incat acesta sa fie un "inceput" de N.

Acesta se poate rafina, eliminand operatii redundante, dupa cum vom vedea in cele ce urmeaza.