AcWing 897. 最长公共子序列
原题链接
简单
作者:
_empty
,
2019-09-24 20:08:39
,
所有人可见
,
阅读 680
LCS 问题
- 时间复杂度:$O(n*m)$。 $n,m分别为两个序列的长度$。
/*LCS : longest common sequence 最长公共子序列问题*/
/*
状态转移:
f[i][j]=0 (i==j==0)
f[i][j]=f[i-1][j-1] (a[i]==b[j]);
f[i][j]=max(f[i][j-1],f[i-1][j]);
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;
char a[N],b[N];
int f[N][N];
int main()
{
int la,lb;
cin>>la>>lb;
cin>>a+1>>b+1;
for(int j=1;j<=lb;j++)
for(int i=1;i<=la;i++)
if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
cout<<f[la][lb]<<endl;
return 0;
}