h1(#Subpermutari). 'H. Subpermutari':problema/Subpermutari

?

Consideram toate cele N² subsecventele are permutarii noastre. Observam faptul ca daca pentru o secventa [a,b] determinam cea mai lunga subpermutare care este atat prefix, cat si sufix a secventei noastre, putem foarte usor marca sufixul ca fiind o secventa care a mai aparut deja si crestem frecventa prefixului.
Pentru a determina cea mai lunga subpermutare care este atat prefix, cat si sufix, vom aplica un algoritm foarte asemanator KMP-ului:
Fixam pozitia de start a subsecventei noastre si pornim algoritmul de KMP de acolo.
Presupunem ca avem calculat pentru o subsecventa [a,b] acest cel mai bun prefix-sufix (il notam identic ca la KMP cu pi[b]). Cand vrem sa trecem la urmatorul element, b + 1, avem aceleasi 2 cazuri de luat in considerare ca si la KMP:
 
Cazul in care elementul inserat b + 1 are aceelasi indice in subpermutarea sufixului ca si urmatorul element in subpermutarea prefixul: pur si simplu pi-ul creste cu 1
Daca indicele difera, micsoram pi-ul (mergem in pi[pi[b]]) si repetam procedeul pana avem o potrivire
 
Pentru a determina al catelea element se afla o valoare intr-o secventa putem usor precalcula cu un simplu aib.
Complexitate: O(N² log N)

h1(#NucleulValoros2). 'I. NucleulValoros2':problema/NucleulValoros2