h2. 'Strigat':problema/strigat

Vom construi un "automat finit":Automate-finite-si-KMP ce va contine cuvintele din intrare. Fiecarei stari din automat ii vom asocia o valoare egala cu suma gradelor de spaima ale cuvintelor acceptate de acea stare. Pentru a determina sirul cu grad maxim de spaima vom construi matricea $A[i][j]$ cu semnificatia care este gradul de spaima maxim pentru un sir de lungime $i$, aflandu-ne la sfarsit in starea $j$ a automatului. Aflandu-ne pe linia $i$ a matricei vom folosi matricea de tranzitie a automatului $δ$ pentru a calcula valorile de pe linia $i + 1$.
 
$A[i + 1][ δ{~j, c~} ] = max( A[i + 1][ δ{~j, c~} ], A[i][j] + ValoareStare[ δ{~j, c~} ] )$, $c ∈ Σ$
 
Constructia automatului are complexitatea $O(L * |Σ|)$, unde $L$ reprezinta suma lungimilor cuvintelor de la intrare si $Σ$ reprezinta alfabetul.
Calcularea matricei are complexitatea $O(N * L * |Σ|)$.
 

h2. 'Flux':problema/flux
Vom forma un sistem de ecuatii in care necunoscutele {$X{~i~}$} vor fi suma fluxurilor de pe drumul de la $0$ la nodul {$i$} (care se garanteaza ca este aceeasi indiferent de drum). Fluxul trimis de la $i$ la $j$ va fi exact {$n{~i,j~}*(X{~j~}-X{~i~})$} unde n{~i,j~} este numarul de muchii dintre $i$ si {$j$}. Vom pune conditiile de conservare a fluxului pentru fiecare nod {$i$}: suma fluxurilor care intra sa fie egala cu suma fluxurilor care ies. Pentru nodul $1$ nu este necesar sa scriem ecuatia deoarece se stie {$X{~1~}=0$}, iar pentru nodul $N$ vom pune ecuatia suma fluxurilor care intra in el sa fie $1$. Sistemul de {$N-1$} ecuatii cu {$N-1$} necunoscute se rezolva folosind Gauss.