h2(#conexiuni). 'Conexiuni':problema/conexiuni

Problema se rezolvă prin programare dinamică, mai precis $D[i][j]$ este lungimea celei mai lungi secvenţe comune ce se termină pe poziţia $i$ în primul şir, respectiv pe poziţia $j$ în al doilea şir. Recurenţa este $D[i][j] = D[i-1][j-1]+1$, dacă $A[i] = B[j]$, sau $0$ altfel. Odată ce am determinat pentru poziţiile $i$ şi $j$ cea mai lungă secvenţă, este clar că va trebui să adunăm la rezultat toate secvenţele ce au lungimea între $1$ şi cea mai mare lungime. Complexitatea finală este $O(N*M)$. Problema mai admite si o alta solutie bazata pe algoritmul KMP, tot in complexitate $O(N*M)$, care obtine 100 puncte. O alta solutie bazata pe Rabin-Karp, desi mentinand complexitatea la $O(N*M)$, merge in practica foarte greu datorita operatiilor modulo care trebuiesc efectuate si se pare ca nu poate obtine prea usor 100 puncte.

Problema se rezolvă prin programare dinamică, mai precis $D[i][j]$ este lungimea celei mai lungi secvenţe comune ce se termină pe poziţia $i$ în primul şir, respectiv pe poziţia $j$ în al doilea şir. Recurenţa este $D[i][j] = D[i-1][j-1]+1$, dacă $A[i] = B[j]$, sau $0$ altfel. Odată ce am determinat pentru poziţiile $i$ şi $j$ cea mai lungă secvenţă, este clar că va trebui să adunăm la rezultat toate secvenţele ce au lungimea între $1$ şi cea mai mare lungime. Complexitatea finală este $O(N*M)$