[ABC141E] Who Says a Pun? 题解

题目链接：[ABC141E] Who Says a Pun?

题意：

给定长度为 \(N\) 的字符串 \(S\) 。找出在 \(S\) 中作为连续子串出现两次或更多次的非空字符串的最大长度，且这些子串不重叠。更正式地说，找到满足以下条件的最大正整数 len ，使得存在整数 \(l_1\) 和 \(l_2\) \((1 \leq l_1, l_2 \leq N-\text{len}+1)\) ，满足：

• \(l_1 + \text{len} \leq l_2\)
• 对于 \(i=0,1, \ldots, \text{len} -1\) ，有 \(S[l_1+i] = S[l_2+i]\) 。

如果不存在这样的整数 len ，则输出0。

数据范围：

\(2 \leq N \leq 5 \times 10^3,~|S| = N\) 。 \(S\) 由小写英文字母组成。

考虑二分这个最大长度，然后用哈希检验。注意这道题要求不重叠，所以要注意一下。

如果用双哈希的话会稍微慢一丢丢，不过我还是用了（大雾）

时间复杂度 \(\mathcal{O}(n^2\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))

const int hash_base[2] = {13, 7};
const int hash_mod[2] = {1000000009, 998244853};

char s[N]; map<pii,int> mp;
int n,hsh[2][N],pwd[2][N];
void init()
{
    for(int c = 0; c < 2; c++)
    {
        int base = hash_base[c], mod = hash_mod[c];
        hsh[c][0] = pwd[c][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            pwd[c][i] = pwd[c][i - 1] * base % mod;
            hsh[c][i] = (hsh[c][i - 1] + s[i]) * base % mod;
        }
    }
}
pii query(int l,int r)
{
    return {
        (hsh[0][r] - hsh[0][l - 1] * pwd[0][r - l + 1] % hash_mod[0] + hash_mod[0]) % hash_mod[0],
        (hsh[1][r] - hsh[1][l - 1] * pwd[1][r - l + 1] % hash_mod[1] + hash_mod[1]) % hash_mod[1]
    };
}
bool check(int len)
{
    mp.clear();
    for(int i = 1; i + len - 1 <= n; i++)
    {
        pii x = query(i, i + len - 1);
        if(mp.count(x) && mp[x] < i) return true;
        else if(!mp.count(x)) mp[x] = i + len - 1;
    }
    return false;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1); init(); int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        check(mid) ? l = mid : r = mid - 1; 
    }
    cout << (check(l) ? l : 0) << '\n';
    return 0;
}