最长公共子串 动态规划
题目
给定2个字符串，试求出这2个字符串的最长公共子串的长度。
输入格式
输入共2行，每行一个字符串。字符均为小写英文字母。
输出格式
仅一行，包含一个正整数，表示2个字符串的最长公共子串长度。
输入样例
ababc
cbaab
输出样例
2
数据范围与提示:
对于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;}
