最长公共子串动态规划

题目

给定2个字符串，试求出这2个字符串的最长公共子串的长度。

输入格式

输入共2行，每行一个字符串。字符均为小写英文字母。

输出格式

仅一行，包含一个正整数，表示2个字符串的最长公共子串长度。

输入样例

ababc
cbaab

输出样例

数据范围与提示:

对于30%的数据，保证字符串长度不超过10；对于60%的数据，保证字符串长度不超过100；对于90%的数据，保证字符串长度不超过1000；对于100%的数据，保证字符串长度不超过5000；

动态规划三步骤

动态规划三步骤
在这里插入图片描述
思路：将两个字符串组合成如上图的二维数组，首先定义一个dp二维数组并明确其定义，dp[i][j]的含义是第i，j位置的最长公共子串的长度。然后确定递推公式，我们思考元素之间的关系是什么，如图可以看出来如果连着匹配字符串，那么dp[i][j]=dp[i-1][j-1]+1,就是在斜对角线加1。我们再思考一下就会发现，当第一行或第一列对应元素相等的时候，是只能等于1的。这时候就需要初始化，当第一行或第一列元素对应相等时，dp[i][j]置为1。

代码

#include<bits/stdc++.h>
using namespace std;
int dp[5001][5001];    //要定义成全局变量，不然会栈溢出
int main(){string a,b;int asize,bsize,maxnum=-1;cin >> a >>  b;asize=a.size();         //获得字符串长度   a.size()bsize=b.size();for(int i=0;i<asize;i++)for(int j=0;j<bsize;j++){if(a[i]!=b[j])          //第一种情况：a[i]!=b[j]dp[i][j]=0;else {                 //第二种情况：a[i]==b[j]if(i==0 || j==0)        //第一行第一列相等为1dp[i][j]=1;elsedp[i][j]=dp[i-1][j-1]+1;       //对角线加一}maxnum=max(dp[i][j],maxnum);//获得最大值}cout << maxnum;return 0;
}