最长公共子串 动态规划
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
if(s1.size() > s2.size()) //以短的作为s1
swap(s1,s2);
int len1 = s1.size(), len2 = s2.size();
int start = 0, mx = 0; //记录结果
vector<vector<int> > dp(len1+1,vector<int>(len2+1,0));
初始化第0行
for j=0; j<len2; j++
if s1[0] == s2[j]
dp[0][j] = 1
初始化第0列
for i=0; i<len1; i++
if s2[0] == s1[i]
dp[i][0] = 1
下标从1开始，因为i,j依赖于 i-1,j-1
for(int i = 1;i<=len1;i++){
for(int j = 1;j<=len2;j++){
字符相同，计数加1，且依赖于以上一个位置结尾的最长公共子串
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > mx){
mx = dp[i][j];
start = i - mx;
}
}
}
cout<<s1.substr(start,mx);
return 0;
}