算法1
(双序列) $O(n*m)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n,m;
char A[1010],B[1010];
cin>>n>>m;
cin>>A>>B;
int f[n+1][m+1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if( i == 0 || j == 0){
f[i][j] = 0;
continue;
}
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(A[i - 1] == B[j - 1])
f[i][j] = f[i - 1][j - 1] + 1;
}
}
cout<<f[n][m];
return 0;
}