最长公共子串 动态规划

#include
#include
#include
#include
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 > dp(len1+1,vector(len2+1,0));

 

初始化第0行

for j=0; j

  if s1[0] == s2[j]

       dp[0][j] = 1

初始化第0列

for i=0; 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<     return 0;
}