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.
