题解 | #查找两个字符串a,b中的最长公共子串#

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        if(s1.size()>s2.size()){
            swap(s1, s2);
        }
        int m=s1.size();
        int n=s2.size();
        int dp[m+1][n+1];
        int len=0,right=0;
        for(int i=0;i<m;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=0;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=0;
                }
                if(dp[i][j]>len){
                    len=dp[i][j];
                    right=i;
                }
            }
        }
        cout<<s1.substr(right-len,len)<<endl;
        
    }
    return 0;
}

动态规划的思路： 1.读取两个字符串并将短的定义为s1，长的为s2； 2.定义二维数组dp[m+1][n+1]保存当前公共子串长度，其中m,n为两字符串长度，dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子串； 3.初始化dp数组。由于空字符串与任意字符串的公共子串长度为0，故dp[i][0]和dp[0][j]都等于0； 4.求出状态转移方程。对于当前s1的第i个字符与s2的第j个字符，若它们相等，则公共子串在dp[i-1][j-1]的基础上加1，若不相等，逻辑上说明最长公共子串长度不变，但是因为子串要连续相等，所以dp[i][j]等于0； 5.每次得出dp[i][j]以后与最大长度比较，若是超过当前已经存储长度，因为只用考虑第一个最长公共子串，所以当相等时也不予考虑(ps:若是有好几个最长公共子串都要输出时，应当定义一个数组保存右端点)则更新最大长度len=dp[i][j]，这时候最长公共子串为s1第i个字符往左数长度为len的子串； 6.输出s1从i-len开始长度为len的子串。