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

#include <iostream>
#include<vector>
using namespace std;
//动态规划，dp[i][j]代表以s[i-1]和t[j-1]结尾的最长公共子串
//状态转移：如果s[i-1]==t[j-1]，则dp[i][j]=dp[i-1][j-1]+1;如果不相等则dp[i][j]=0;
//边界条件：dp[0][j]=0;dp[i][0]=0;
int main() {
    string s,t;
    cin>>s>>t;
    int m=s.size();
    int n=t.size();
    int maxlen=0;//记录最长的公共子串长度
    int pos=300;//记录了最长子串的结尾位置
    vector<vector<int>>dp(m+1,vector<int>(n+1,0));
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(s[i-1]==t[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                if(maxlen<=dp[i][j])
                {
                    int tmp= m>=n? j-1 : i-1 ;//记录最长公共子串结尾在较短串中的位置
                    if(maxlen<dp[i][j] || tmp<pos)//两种情况需要更新结尾位置
                        pos=tmp;
                    maxlen=dp[i][j];//更新最大值
                }
            }
            else
                dp[i][j]=0;
        }
    }
    //输出最长公共子串
    if(m>=n)   
    {
        for(int i=pos-maxlen+1; i<=pos; i++)   
            cout<<t[i];
    }
    else
    {
        for(int i=pos-maxlen+1; i<=pos; i++)   
            cout<<s[i];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")