h3. Algoritm_calcul_functie_prefix

1: n <- lungime(N)
2: k <- 0
3: p[1] <- 0
4: pt i <- 2, n
5: cat timp (k > 0) si (N[k + 1] ** N[i])
6: k <- p[k]
7: daca N[k + 1] = N[i]
8: k <- k + 1
9: p[i] <- k

== code(c) |
n <- lungime(N)
k <- 0
&#960;[1] <- 0
pt i <- 2, n
    cat timp (k > 0) si (N[k + 1] ** N[i])
        k <- &#960;[k]
    daca N[k + 1] = N[i]
        k <- k + 1
    &#960;[i] <- k
==

Analiza complexitatii :
- la fiecare pas (i = 2, n) k se incrementeaza cel mult o data, deci pe parcursul algoritmului k se va incrementa de cel mult n - 1 ori (linia 8)