Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-05-28 21:22:58.
Revizia anterioară   Revizia următoare  

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)