Опишу-ка я некоторые алгоритмы которые "я всегда знал но забыл".
Начнем с длины самой длинной общей подпоследовательности.
Пусть у нас есть два массива A=(a1...ai) и B=(b1...bj)
Тогда LCS(A,B)=:
1. 0 если i==0 или j==0;
2. LCS((a1...ai-1) ,(b1...bj-1))+1, если ai==bj
3. MAX(LCS((a1...ai-1) ,(b1...bj)),LCS((a1...ai) ,(b1...bj-1))), если ai!=bj
Это достаточно очевидные утверждения, и по ним уже можно составить алгоритм.
Алгоритм просто напрашивается:
int lcs(int* a,int N1,int* b,int N2)
{
if(N1==0 && N2==0)
return 0;
if(a[N1-1) == b[N2-1])
return 1+lcs(a,N1-1,b,N2-1);
return max(lcs(a,N1,b,N2-1),lcs(a,N1-1,b,N2))
}
красотища...если бы не одно но. очень медленно.
И в целом почти сразу понятно почему. Мы не храним промежуточные вычисления а каждый раз делаем их заново.
Класический пример такой проблемы - вычесление чилес Фибоначчи по рекурсии:
int F(int N)
{
return (N<2)?1:F(N-2)+F(N-1);
}
Улучшить это можно, сохраняя промежуточные результаты вычислений. Этот прием называется "меморизация". Т.е. вообще-то он называется "
Memoization", но надо же как-то по русски сказать.
В данном случае для меморизации нам понадобится массив размером [i*j].
Но тут возникает интересный вопрос - а зачем нам тогда рекурсия здалась?
И возникает примерно такой код (пробывать не советую, не тестировал, могу ошибиться с индексами)
int lcs_array(int* a,int N1,int* b,int N2)
{
int* c = new int[N1*N2];
memset(c,0,N1*N2*sizeof(int));
for(int i=0;i<N1;++i)
for(int j=0;j<N2;++j)
c[i*N2+j]=(a[i]==b[j])?c[(i-1)*N2+j-1]+1:max(c[i*N2+j-1],c[(i-1)*N2+j]);
int res = c[N1*N2-1];
delete[] c;
return res;
}