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)