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

δ(q, c) = i

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

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

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.

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$}.

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