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

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 ∈ Σ$

$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 * |Σ|)$.