摘要
Title: HJ65 查找两个字符串a,b中的最长公共子串
Tag: 最长公共子串
Memory Limit: 64 MB
Time Limit: 1000 ms

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

题意

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
思路

参考这篇我之前写的文章 blog，使用字符串哈希和二分实现的

这里用dp实现：
- f[i][j]表示 1~ai,1~bj且ai,bj为结尾的所有公共子串
- 属性：最长公共串长度
- 转移：
  - 如果ai==bj且ai,bj都是字母，则f[i][j]=f[i-1][j-1]+1
  - 其他，f[i][j]=0
优化：类似01背包问题，考虑i: 1~alen枚举，j: blen~1倒序枚举，即可优化一维

这里引文要输出较短串中最先出现，所以要先辨别出短的串

代码

#include <any>
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int dp[N];

signed main()
{
    //freopen("Tests/input_1.txt", "r", stdin);
    IOS;

    string a, b;
    cin >> a >> b;

    int n = SZ(a), m = SZ(b);

    if (n > m){
        swap(a, b);
        swap(n, m);
    }    

    a = " " + a;
    b = " " + b;

    int mx = 0, end = -1;
    for(int i = 1; i <= n; ++ i){
        for(int j = m; j >= 1; -- j){
            if(a[i] == b[j]){
                dp[j] = dp[j - 1] + 1;
                if(dp[j] > mx){
                    mx = dp[j];
                    end = i;
                }
            }
            else dp[j] = 0;
        }
    }

    cout << a.substr(end - mx + 1, mx);


    return 0;
}

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

题意

思路

代码