摘要
Title: 3508. 最长公共子串
Tag: 二分、字符串哈希
Memory Limit: 64 MB
Time Limit: 1000 ms

3508. 最长公共子串

题意

给定两个字符串，求这两个字符串的不包含数字的最长公共子串的长度。
思路

首先可以采用dp的方法暴力来做，复杂度为 $O(n^2)$
其次考虑二分，因为答案具有单调性，所以，可以在二分时将一个串的长度为mid的串的哈希值存在哈希表中，扫另一个串时进行判断有没有
最后不包含数字这一条，可以将每个串的数字各替换成不同的符号

代码

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

#define ULL unsigned long long

#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, P = 13331;
ULL hs[N], ps[N], ht[N], pt[N];
string s, t;

ULL gets(int l, int r)
{
    return hs[r] - hs[l - 1] * ps[r - l + 1];
}
ULL gett(int l, int r)
{
    return ht[r] - ht[l - 1] * pt[r - l + 1];
}

bool check(int x)
{
    unordered_set <int> us;
    for(int i = 1; i + x - 1 < SZ(s); ++ i){
        us.insert(gets(i, i + x - 1));
    }
    for(int i = 1; i + x - 1 < SZ(t); ++ i){
        if(us.count(gett(i, i + x - 1))) return true;
    }
    return false;
}

signed main()
{
    IOS;

    cin >> s >> t;

    s = " " + s;
    t = " " + t;

    for(int i = 1; i < SZ(s); ++ i){
        if(s[i] >= '0' && s[i] <= '9') s[i] = '#';
    }

    for(int i = 1; i < SZ(t); ++ i){
        if(t[i] >= '0' && t[i] <= '9') t[i] = '$';
    }

    ps[0] = pt[0] = 1;
    for(int i = 1; i < SZ(s); ++ i){
        ps[i] = ps[i - 1] * P;
        hs[i] = hs[i - 1] * P + s[i];
    }

    for(int i = 1; i < SZ(t); ++ i){
        pt[i] = pt[i - 1] * P;
        ht[i] = ht[i - 1] * P + t[i];
    }

    int l = 0, r = min(SZ(s), SZ(t));
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r;
    return 0;
}

3508. 最长公共子串

题意

思路

代码