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

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

int n, m;
string a, b;
int f[N][N];//f[i][j]表示a串前i个字符和b串前j个字符的最长公共子串

int main()
{
    cin>>a>>b;
    n=a.size(), m=b.size();
    a=" "+a, b=" "+b;
    if(n>m) swap(n, m), swap(a, b);
    string ans;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            //f[i][j]=max(f[i-1][j], f[i][j-1]);//状态转移，这两个在一起还包含了f[i-1][j-1]的情况
            if(a[i]==b[j])
            {
                f[i][j]=f[i-1][j-1]+1;
                if(f[i][j]>ans.size()) ans=a.substr(i-f[i][j]+1, f[i][j]);
            }
        }
    cout<<ans;
    
    return 0;
}

#牛客春招刷题训练营#

动态规划可以很好的解决问题，集合表示f[i][j]为a串的前i个字符和b串的前j个字符的最长公共子串长度

转移方程就是f[i][j]=f[i-1][j-1]+1当且仅当a[i]==b[j]时成立，此时可以查看是否更新ans

在更新过程中第一个更新的即为最短串里的答案（题目要求的，所以如果a串比b串长记得swap一下