pi[i] <- k
==

h3.  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$})
* in linia {$5$}, $k$ se decrementeaza cel mult pana devine {$0$}, deci se va decrementa de cel

* 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$})
** in linia {$5$}, $k$ se decrementeaza cel mult pana devine {$0$}, deci se va decrementa de cel

mult $n - 1$ ori pe parcursul algoritmului

 
=> Complexitate : $O(n)$

* Complexitate : $O(n)$

Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare $i$ in care s-a acceptat {$N{~i~}$}, vedem cat de mult putem lua de la sfarsitul lui {$N{~i~}$} astfel incat sufixul respectiv sa fie prefix pentru {$N$}. De remarcat ca in cazul in care starea candidata $k$ nu este buna, nu mergem in {$k - 1$}, ci in {$Π{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.