РЕДАКТИРОВАТЬ : C++
реализация: http://comeoncodeon.wordpress.com/2009/08/07/longest-common-subsequence-lcs/
Существует алгоритм динамического программирования для поиска самой длинной общей подпоследовательности из двух последовательностей (при условии, что вы имели в виду LCS): http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
Вот повторение (из Википедии):
и псевдокод (также из Википедии):
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else:
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
Затем можно восстановить самые длинные подпоследовательности из массива C
(см. Статью в Википедии).