回滚莫队解决 Border 问题

本篇题解参考了 Alex_Wei 的这篇题解中提及到的 Border 的性质。

由这篇文章中提及的性质可以发现，若已知一个字符串的 Border 后，那么在这个字符串头部或者尾部不断加入新的字符，得到的新的字符串的 Border 不会超过原字符串的 Border + 加入的新的字符的个数，但是反过来无法得到类似的性质。这说明字符串的 Border 的具有易增难删的性质，这启示我们使用回滚莫队去单方面维护增的这部分。在回滚莫队指针往两端滚动的时候，我们可以很容易地通过原字符串的 Border 获得新的字符串的 Border 的上界，然后再暴力匹配找到新的字符串的 Border 的真实值，复杂度分析可以参考 Alex_Wei 的这篇题解。

判断字符串是否相等使用哈希。

具体实现见代码部分。再贴一个可以使用回滚莫队解决的字符串好题：2023 CCPC 哈尔滨站 C 题。

#include <bits/stdc++.h>
using namespace std;

#define ios                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);

const int N = 2e5 + 10, mod = 1e9 + 7;

const int base = 131;
int powb[N], hx[N];
int gethx(int l, int r)
{
    --l;
    return (hx[r] - 1ll * hx[l] * powb[r - l] % mod + mod) % mod;
}

char s[N];
int ans[N];
int n, siz, t, m;
int pos[N];
int L[N], R[N];
array<int, 3> qu[N];

void solve()
{
    cin >> s + 1;
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        hx[i] = (1ll * hx[i - 1] * base + s[i]) % mod;

    siz = sqrt(n);
    t = n / siz;
    for (int i = 1; i <= t; i++)
        L[i] = R[i - 1] + 1, R[i] = i * siz;
    R[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i;

    cin >> m;
    for (int i = 1, l, r; i <= m; i++)
    {
        cin >> l >> r;
        qu[i] = {l, r, i};
    }

    sort(qu + 1, qu + m + 1, [&](auto a, auto b)
         { return pos[a[0]] == pos[b[0]] ? a[1] < b[1] : pos[a[0]] < pos[b[0]]; });

    for (int k = 1, i = 1; k <= t; k++)
    {
        int len = 0, r = R[k], l = r + 1;
        for (; pos[qu[i][0]] == k; i++)
        {
            auto [ql, qr, id] = qu[i];
            if (pos[ql] == pos[qr])
            {
                for (int p = 1; p < qr - ql + 1; p++)
                    if (gethx(ql, ql + p - 1) == gethx(qr - p + 1, qr))
                        ans[id] = p;
            }
            else
            {
                l = R[k] + 1; // 重置左指针，不用滚回去
                while (r < qr)
                {
                    ++r;
                    ++len;
                }
                while (len >= r - l + 1 || gethx(l, l + len - 1) != gethx(r - len + 1, r))
                    --len;
                int now = len; // 用 now 来记录在左侧新加入字符后的 Border 
                while (l > ql)
                {
                    --l;
                    now++;
                }
                while (now >= r - l + 1 || gethx(l, l + now - 1) != gethx(r - now + 1, r))
                    --now;
                ans[id] = now;
            }
        }
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
}

signed main()
{
    ios;

    powb[0] = 1;
    for (int i = 1; i < N; i++)
        powb[i] = 1ll * powb[i - 1] * base % mod;

    int t = 1;
    srand(time(0));
    cout << fixed << setprecision(12);

    solve();

    return 0;
}