分析
状态表示
- 集合: f[i][j] 表示a字符串从1~i 与 b字符串从1~j 公共子串的长度
- 属性: 求最长公共子串
状态计算
将集合化为四部分 公共子串最后一个数 包含不包含a[i],包含不包含b[i]
解析:
1. 不包含a[i]且不包含b[j]时:状态转移为求1~i-1, 1~j-1 的公共子串 -> f[i-1][j-1]
2. 包含a[i]且包含b[j]时:可以推断出a,b字符串的长度相同
,最后一个相同那就判断1~i-1, 1~j-1 的公共子串 -> f[i-1][j-1]+1
3. 包含a[i]且不包含b[j]时:不能简单理解为f[i][j-1],因为根据定义f[i][j-1]表示A字符串1~i与B字符串1~j-1的长度,其中可能包含a[i]也可能不包含。之所以在状态转移中写为 -> f[i][j-1]
是因为这个状态中包括3的情况,在保证整体不出大范围的情况下,根据提议取最大值对结果没有影响
4. 同三解释
需要说明的是3,4情况就包括了1情况,可以省略
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;
int main()
{
cin >> n >> m >> a + 1 >> b + 1;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); //注意要保证前提
}
cout << f[n][m] << endl;
return 0;
}