题解 | 查找两个字符串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<int>dp(n+1,0);
    for(int i=1; i<=m; i++)
    {
        int prev=dp[0];//从头开始记录左上位置
        for(int j=1; j<=n; j++)
        {
            int old=dp[j];//记录修改前的值
            if(s[i-1]==t[j-1])
            {
                dp[j]=prev+1;
                if(maxlen<=dp[j])
                {
                    int tmp= m>=n? j-1 : i-1 ;//记录最长公共子串结尾在较短串中的位置
                    if(maxlen<dp[j] || tmp<pos)//两种情况需要更新结尾位置
                        pos=tmp;
                    maxlen=dp[j];//更新最大值
                }
            }
            else
                dp[j]=0;
            //左上记录右移一位
            prev=old;
        }
    }
    //输出最长公共子串
    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")