题解：String

FChang · 2025-05-06 16:33:43 · 题解

前言

我的 std 做法很蠢。

你可以选择用高级的线段树合并做掉它，并且良心出题人没有强制在线。

再次感谢 sunset_breeze 给出的线段树合并解法，Vector 给出的非随机数据下的解法。

solution

对 S 建出回文自动机，然后对于 fail 树做倍增，在建出回文自动机时记录这个回文串第一次出现的位置。

将长度为 len_2 的回文串存在一个 vector 中，根据 fail 的定义，对于每一个长度为 len_2 的回文串，倍增查找是否存在长度为 len_1 的回文前缀，输出之前记录的最靠前的位置即可。

时间复杂度 \mathcal{O}(n \times 15)。

std

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q;
char a[N];
int len[N], fail[N], ch[N][27], cur, pos, tot = 1;
inline int getfail (int x, int i) {
    while (i - len[x] - 1 < 0 || a[i - len[x] - 1] != a[i]) x = fail[x];
    return x;
}
vector <int> e[N], lnk[N];
int f[N][21], dep[N], down[N];
inline void dfs (int x, int fa) {
    f[x][0] = fa, dep[x] = dep[fa] + 1;
    for (int i = 1; i <= 19; ++ i) f[x][i] = f[f[x][i - 1]][i - 1];
    for (auto v : e[x]) {
        if (v == fa) continue;
        dfs (v, x);
    }
    return ;
}
signed main () {
    ios::sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n >> q;
    cin >> (a + 1);
    fail[0] = 1, len[1] = -1;
    e[0].push_back (1), e[1].push_back (0);
    for (int i = 1; i <= n; ++ i) {
        pos = getfail (cur, i);
        if (!ch[pos][a[i] - 'a']) {
            fail[++ tot] = ch[getfail (fail[pos], i)][a[i] - 'a'];
            e[fail[tot]].push_back (tot), e[tot].push_back (fail[tot]);
            ch[pos][a[i] - 'a'] = tot;
            len[tot] = len[pos] + 2;
            down[tot] = i - len[tot] + 1;
            lnk[len[tot]].push_back (tot);
        }
        cur = ch[pos][a[i] - 'a'];
    }
    dfs (1, 1);
    dfs (0, 0);
    for (int i = 1, l, r; i <= q; ++ i) {
        cin >> l >> r;
        int ans = n + 1;
        for (auto x : lnk[r]) {
            int val = down[x];
            for (int i = 19; i >= 0; -- i) if (len[f[x][i]] >= l) x = f[x][i];
            if (len[x] == l) {
                ans = min (ans, val);
                break;
            }
        }
        if (ans != n + 1) cout << ans << "\n";
        else cout << "-1\n";
    }
    return 0;
}