回文串

GitHub跳转原题关系图返回列表

把 F 的计数按 |S|≤|T| 与 |S|>|T| 两类拆开,用 Manacher 差分预处理回文前缀/后缀计数,再用哈希二分求 LCP,单次询问 O(log n)。

OJ: roj

题目 ID: 1694

难度:提高+/省选-

标签:字符串Manacher哈希二分前缀和python

创建: 2026-10-07 15:50

更新: 2026-10-07 15:50

形式化题目

给定两个串 AA、BB,记 AxA_x 为 AA 的第 xx 长后缀(长度 n−x+1n-x+1),ByB_y 为 BB 的第 yy 长前缀 (长度 m−y+1m-y+1)。F(Ax,By)F(A_x,B_y) 是满足下面条件的二元组 (S,T)(S,T) 个数:

  • SS 是 AxA_x 的非空前缀,TT 是 ByB_y 的非空后缀;
  • 把 SS 与 TT 拼接后得到的串 S+TS+T 是回文串。

有 QQ 组询问,每组给 xi,yix_i,y_i,求 F(Axi,Byi)F(A_{x_i},B_{y_i})。输入的 xx 用 1 起下标 (x=1x=1 表示整个 AA),yy 也用 1 起下标(y=1y=1 表示整个 BB)。

把下标换成 0 起会好写很多:令

st=x−1,L=m−y+1,st = x-1,\qquad L = m-y+1,

则 Ax=A[st..n−1]A_x = A[st..n-1],By=B[0..L−1]B_y = B[0..L-1]。∣S∣=p|S|=p 时 S=A[st..st+p−1]S=A[st..st+p-1], ∣T∣=q|T|=q 时 T=B[L−q..L−1]T=B[L-q..L-1]。题目要的就是"使 S+TS+T 回文的 (p,q)(p,q) 对数"。

数据分三档类型:AA 是串随机,BB 是串随机且 ∣B∣⩽104|B|\leqslant 10^4,CC 无特殊性质。 满分档是 A,B,CA,B,C 在 ∣A∣,∣B∣⩽8×105|A|,|B|\leqslant 8\times 10^5、Q⩽105Q\leqslant 10^5 上都成立, 所以正解不能依赖任何随机性。

正解

思路

先固定一个查询看结构。 设 PP 是 A[st..]A[st..] 与 rev⁡(B)[y−1..]\operatorname{rev}(B)[y-1..] 的最长公共前缀长度 (注意 rev⁡(B)\operatorname{rev}(B) 的下标 y−1y-1 恰好对应 ByB_y 的最后一个字符 B[L−1]B[L-1])。 把 S+TS+T 按 pp 与 qq 的大小分成两类,两类的形态完全不同:

匹配段 中间段 计数
p⩽qp\leqslant q SS 与 TT 的长度 pp 的后缀必须互为逆序 TT 去掉末尾 pp 个字符,即 B[L−q..L−p−1]B[L-q..L-p-1] 每个 pp 贡献 cntB[L−p]+1\mathrm{cntB}[L-p]+1
p>qp>q TT 与 SS 的长度 qq 的前缀必须互为逆序 SS 去掉开头 qq 个字符,即 A[st+q..st+p−1]A[st+q..st+p-1] 每个 qq 贡献 fA[st+q]\mathrm{fA}[st+q]

两类的第一个条件都只是"SS 的开头与 TT 的末尾互为逆序":SS 的开头是 A[st..]A[st..] 的前缀, TT 的末尾是 rev⁡(B)[y−1..]\operatorname{rev}(B)[y-1..] 的前缀,所以这一个条件在两类里都等价于 p⩽Pp\leqslant P(或 q⩽Pq\leqslant P),PP 对一次询问是同一个数。

为什么中间段回文就够了? 以 p⩽qp\leqslant q 为例,拼接结果是 S⏟长 p  M  T 的末尾 p 个字符⏟=rev⁡(S)\underbrace{S}_{\text{长 }p}\;M\;\underbrace{T\text{ 的末尾 }p\text{ 个字符}}_{=\operatorname{rev}(S)}, 其中 M=AM=A 里那 pp 个字符之外的 B[L−q..L−p−1]⏟长 q−p\underbrace{B[L-q..L-p-1]}_{\text{长 }q-p}。 一个串是回文当且仅当"掐掉对称的两端后剩下的中间仍是回文", 而 rev⁡(S)+M+S\operatorname{rev}(S)+M+S 结构中,SS 与 rev⁡(S)\operatorname{rev}(S) 已经配平, 所以整串回文   ⟺  \iff 中间段 MM 回文。这也是本题能拆成"匹配 + 回文计数"的原因。

两个回文计数表。 定义

cntB[e]=B[1..e] 的非空回文后缀个数,fA[i]=A[i..] 的非空回文前缀个数.\mathrm{cntB}[e] = B[1..e] \text{ 的非空回文后缀个数}, \qquad \mathrm{fA}[i] = A[i..] \text{ 的非空回文前缀个数}.

那么 p⩽qp\leqslant q 一类里,固定 pp 时中间段是 B[0..L−p−1]B[0..L-p-1] 的一个非空回文后缀 (q=pq=p 时中间段为空,单独算一种),贡献正好是 cntB[L−p]+1\mathrm{cntB}[L-p]+1; p>qp>q 一类里,固定 qq 时中间段是 A[st+q..]A[st+q..] 的一个非空回文前缀,贡献正好是 fA[st+q]\mathrm{fA}[st+q]。 于是

  F(Ax,By)=∑e=L−PL−1(cntB[e]+1)  +  ∑i=x+1x+PfA[i]  \boxed{\;F(A_x,B_y)=\sum_{e=L-P}^{L-1}\bigl(\mathrm{cntB}[e]+1\bigr)\;+\;\sum_{i=x+1}^{x+P}\mathrm{fA}[i]\;}

第一条和式的 ii 换成 p=1..Pp=1..P 就是 e=L−pe=L-p,第二条和式的 1 起下标 i=st+q+1=x+qi=st+q+1=x+q。

两张表怎么 O(n) 求。 cntB\mathrm{cntB} 与 fA\mathrm{fA} 都是"每个回文子串给一个端点记一次"。 Manacher 求出 d1,d2d_1,d_2 后,中心 ii 的奇回文串恰好覆盖起点区间 [i−d1[i]+1, i][i-d_1[i]+1,\,i] 和终点区间 [i+1, i+d1[i]][i+1,\,i+d_1[i]](下标换成 1 起同理),偶回文串覆盖 [i−d2[i], i−1][i-d_2[i],\,i-1] 与 [i+1, i+d2[i]][i+1,\,i+d_2[i]]。 对每个区间做一次差分加一,最后取前缀和,就得到"每个位置作为回文前缀起点出现多少次"与 “每个位置作为回文后缀终点出现多少次”。再各自做一次前缀和,两条和式都能 O(1)O(1) 求。

PP 怎么求。 单次询问的 PP 是变化的,用双底数滚动哈希判等加二分:二分长度 midmid, 比较 A[st..st+mid−1]A[st..st+mid-1] 与 rev⁡(B)[y−1..y−1+mid−1]\operatorname{rev}(B)[y-1..y-1+mid-1] 的哈希值即可。 双底数(两个大奇数基数、模 2642^{64} 自然溢出)避免被单底数构造卡掉。

边界处理。 PP 的上界取 min⁡(n−st, L)\min(n-st,\,L):SS 不能超出 AA,TT 不能超出 ByB_y。 注意 L−PL-P 可能等于 00(此时第一项只含 e=0e=0,即 cntB[0]+1=1\mathrm{cntB}[0]+1=1,对应 q=p=Lq=p=L 的空中间段), 而 x+Px+P 可能等于 n+1n+1(此时第二项的下标越出 AA,令 fA[n+1]=0\mathrm{fA}[n+1]=0 即可)。 两个前缀和数组都多留一格,O(1)O(1) 取值不会越界。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:45
# update_at: 2026-10-07 15:50

import sys
from itertools import accumulate

MASK = (1 << 64) - 1   # 滚动哈希按 2^64 自然溢出:乘法后取低 64 位
BASE = 1315423911      # 哈希基数,取一个大奇数,与 main.cpp 的底数一致

# 类型别名:Manacher 返回 (d1, d2),build_hash 返回 (前缀哈希, 幂表),都是这个形状
type TwoTables = tuple[list[int], list[int]]
# Prep 打包一组询问要用到的全部预处理表,字段依次是:
# (|A|, |B|, fA 前缀和, (cntB+1) 前缀和, A 哈希表, rev(B) 哈希表, BASE 幂表)
type Prep = tuple[int, int, list[int], list[int], list[int], list[int], list[int]]


def manacher(s: bytes) -> TwoTables:
    """返回 (d1, d2):d1[i] 是以 i 为中心的最长奇回文半径,d2[i] 是以 i-1、i 为中心的最长偶回文半径。"""
    size = len(s)
    d1 = [0] * size
    left, right = 0, -1
    for i in range(size):
        k = 1 if i > right else min(d1[left + right - i], right - i + 1)
        while i - k >= 0 and i + k < size and s[i - k] == s[i + k]:
            k += 1
        d1[i] = k
        if i + k - 1 > right:
            left, right = i - k + 1, i + k - 1

    d2 = [0] * size
    left, right = 0, -1
    for i in range(size):
        k = 0 if i > right else min(d2[left + right - i + 1], right - i + 1)
        while i - k - 1 >= 0 and i + k < size and s[i - k - 1] == s[i + k]:
            k += 1
        d2[i] = k
        if i + k - 1 > right:
            left, right = i - k, i + k - 1
    return d1, d2


def prefix_pal_counts(s: bytes) -> list[int]:
    """counts[i] = s[i:] 的非空回文前缀个数(1-based 下标,末尾补一个 0)。"""
    size = len(s)
    d1, d2 = manacher(s)
    diff = [0] * (size + 2)
    for i in range(size):
        # 奇回文 s[i-k+1..i+k-1] 的起点落在 [i-d1[i]+1, i]
        diff[i - d1[i] + 1] += 1
        diff[i + 1] -= 1
        if d2[i]:
            # 偶回文 s[i-k..i+k-1] 的起点落在 [i-d2[i], i-1]
            diff[i - d2[i]] += 1
            diff[i] -= 1
    counts = [0] * (size + 2)   # 每个回文子串只给它的起点记一次,差分摊平后取前缀和
    cur = 0
    for i in range(size):
        cur += diff[i]
        counts[i + 1] = cur
    return counts


def suffix_pal_counts(s: bytes) -> list[int]:
    """counts[e] = s[:e] 的非空回文后缀个数(e = 0..len(s))。"""
    size = len(s)
    d1, d2 = manacher(s)
    diff = [0] * (size + 2)
    for i in range(size):
        # 奇回文的结束位置落在 [i+1, i+d1[i]],偶回文落在 [i+1, i+d2[i]]
        diff[i + 1] += 1
        diff[i + d1[i] + 1] -= 1
        if d2[i]:
            diff[i + 1] += 1
            diff[i + d2[i] + 1] -= 1
    counts = [0] * (size + 1)
    cur = 0
    for e in range(1, size + 1):
        cur += diff[e]
        counts[e] = cur
    return counts


def build_hash(s: bytes) -> TwoTables:
    """返回 s 的前缀哈希表与 BASE 的幂表。"""
    size = len(s)
    h = [0] * (size + 1)
    for i, ch in enumerate(s):
        h[i + 1] = (h[i] * BASE + ch) & MASK
    power = [1] * (size + 1)
    for i in range(1, size + 1):
        power[i] = power[i - 1] * BASE & MASK
    return h, power


def prepare(a: bytes, b: bytes) -> Prep:
    """预处理两串:回文计数的前缀和表,加上 A 与 rev(B) 的滚动哈希表。"""
    rev_b = b[::-1]   # B_y 的匹配方向就是 B 的逆序
    # accumulate(prefix_pal_counts(a)) 即 fA 的前缀和,恰好多留一格支持 x+P = n+1
    pre_f = list(accumulate(prefix_pal_counts(a)))
    # 每个匹配长度 e 都额外贡献一种"中间段为空"的取法,所以计数是 cntB[e]+1
    pre_e = list(accumulate((c + 1 for c in suffix_pal_counts(b)), initial=0))
    hash_a, power = build_hash(a)
    hash_r, _ = build_hash(rev_b)
    return len(a), len(b), pre_f, pre_e, hash_a, hash_r, power


def longest_common_prefix(hash_a: list[int], hash_r: list[int], power: list[int],
                          st: int, yst: int, limit: int) -> int:
    """二分求 A[st..] 与 rev(B)[yst..] 的最长公共前缀长度,长度上限为 limit。"""
    lo, hi = 0, limit
    while lo < hi:
        mid = (lo + hi + 1) >> 1
        # 两串各取 mid 个字符的区间哈希,相等就认为这 mid 个字符匹配
        left = (hash_a[st + mid] - hash_a[st] * power[mid]) & MASK
        right = (hash_r[yst + mid] - hash_r[yst] * power[mid]) & MASK
        if left == right:
            lo = mid
        else:
            hi = mid - 1
    return lo


def count_pairs(prep: Prep, x: int, y: int) -> int:
    """回答一组询问:F(A_x, B_y) 的值。"""
    n, m, pre_f, pre_e, hash_a, hash_r, power = prep
    st = x - 1                       # A_x 在 A 中的起点(0-based)
    length = m - y + 1               # B_y 的长度
    common = longest_common_prefix(hash_a, hash_r, power, st, y - 1, min(n - st, length))
    # |S| <= |T| 的 p = 1..common 段 + |S| > |T| 的 q = 1..common 段
    return (pre_e[length] - pre_e[length - common]) + (pre_f[x + common] - pre_f[x])


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    dtype = next(data)   # 第一行是数据类型,三档数据共用同一套算法,只做占位
    prep = prepare(next(data), next(data))

    q = int(next(data))
    out: list[str] = []
    for _ in range(q):
        x = int(next(data))
        y = int(next(data))
        out.append(str(count_pairs(prep, x, y)))
    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:45
 * update_at: 2026-10-07 15:50
 */
// main.cpp:回文串(一本通 1694)。
//
// 记 A_x 为 A 的第 x 长后缀(长度 n-x+1),B_y 为 B 的第 y 长前缀(长度 m-y+1)。
// 对询问 (x,y) 取 st = x-1、L = m-y+1、P = LCP(A[st..], rev(B)[y-1..]),把方案按 |S|、|T| 分类:
//   |S| <= |T|:匹配段要求 |S| <= P,去掉末尾 |S| 个字符后剩下的中段须回文,
//               于是每个 p = 1..P 贡献 cntB[L-p]+1 种,合计 sum_{e=L-P}^{L-1}(cntB[e]+1);
//   |S| >  |T|:匹配段要求 |T| <= P,去掉开头 |T| 个字符后剩下的中段须回文,
//               于是每个 q = 1..P 贡献 fA[st+q] 种,合计 sum_{q=1}^{P} fA[st+q]。
// 其中 cntB[e] = B[1..e] 的非空回文后缀个数,fA[i] = A[i..] 的非空回文前缀个数,
// 两者都用 Manacher + 差分数组预处理成前缀和,做到 O(1) 求区间和;
// 唯一的动态量 P 用双底数哈希 + 二分求出。

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

typedef long long ll;

const int MAXN = 800005; // |A|、|B| 的上界 8*10^5

char strA[MAXN]; // 原串 A
char strB[MAXN]; // 原串 B
char strR[MAXN]; // rev(B):B_y 的匹配方向正好是 B 的逆序,于是把 B 反过来当第二个串

int n, m; // |A|、|B|

int d1[MAXN]; // Manacher 奇回文半径:d1[i] 表示 s[i] 为中心的最长奇回文半径
int d2[MAXN]; // Manacher 偶回文半径:d2[i] 表示 s[i-1]、s[i] 为中心的最长偶回文半径

ll diff[MAXN]; // 差分数组:把每个回文串对"起点集合 / 终点集合"的贡献压成一次区间加

ll cntStart[MAXN]; // cntStart[i] = A[i..] 的非空回文前缀个数(1-based,i=1..n;cntStart[n+1]=0)
ll preStart[MAXN]; // preStart[i] = cntStart[1..i] 的前缀和
ll cntEnd[MAXN];   // cntEnd[e] = B[1..e] 的非空回文后缀个数(e=0..m,cntEnd[0]=0)
ll preEnd[MAXN];   // preEnd[k] = sum_{e=0}^{k-1} (cntEnd[e]+1)

// 双底数滚动哈希,模 2^64 自然溢出;hash[0] 用 BASE1、hash[1] 用 BASE2
const unsigned long long BASE1 = 1315423911ULL;
const unsigned long long BASE2 = 2654435761ULL;
unsigned long long hashA[2][MAXN]; // hashA[k][i] = A 前 i 个字符的哈希值
unsigned long long hashR[2][MAXN]; // hashR[k][i] = rev(B) 前 i 个字符的哈希值
unsigned long long power[2][MAXN]; // power[k][i] = BASE_{k+1}^i

// Manacher:求串 s 的奇偶回文半径,结果放进全局 d1/d2,两个串依次复用
void manacher(const char *s, int len) {
    for (int i = 0, l = 0, r = -1; i < len; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < len && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    for (int i = 0, l = 0, r = -1; i < len; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < len && s[i - k - 1] == s[i + k]) k++;
        d2[i] = k;
        if (i + k - 1 > r) { l = i - k; r = i + k - 1; }
    }
}

// 预处理 fA:把"每个回文子串给它的起点记一次"用差分数组摊平,再取前缀和
void build_start(const char *s, int len) {
    manacher(s, len);
    for (int i = 0; i <= len + 1; i++) diff[i] = 0;
    for (int i = 0; i < len; i++) {
        // 奇回文 s[i-k+1..i+k-1],k=1..d1[i]:起点落在 [i-d1[i]+1, i]
        diff[i - d1[i] + 1] += 1;
        diff[i + 1] -= 1;
        // 偶回文 s[i-k..i+k-1],k=1..d2[i]:起点落在 [i-d2[i], i-1]
        if (d2[i] > 0) {
            diff[i - d2[i]] += 1;
            diff[i] -= 1;
        }
    }
    ll cur = 0;
    for (int i = 0; i < len; i++) {
        cur += diff[i];
        cntStart[i + 1] = cur; // 起点 i(0-based)对应 1-based 下标 i+1
    }
    cntStart[len + 1] = 0; // 空后缀没有回文前缀,正好支持 x+P = n+1 的取值
    preStart[0] = 0;
    for (int i = 1; i <= len + 1; i++) preStart[i] = preStart[i - 1] + cntStart[i];
}

// 预处理 cntB:回文串给它的结束位置记一次;再写成 preEnd[k] = sum_{e<k}(cntB[e]+1)
void build_end(const char *s, int len) {
    manacher(s, len);
    for (int i = 0; i <= len + 1; i++) diff[i] = 0;
    for (int i = 0; i < len; i++) {
        // 奇回文结束位置 e 落在 [i+1, i+d1[i]](e 为 1-based 的结束下标)
        diff[i + 1] += 1;
        diff[i + d1[i] + 1] -= 1;
        // 偶回文 s[i-k..i+k-1],k=1..d2[i]:结束位置同样是 [i+1, i+d2[i]]
        if (d2[i] > 0) {
            diff[i + 1] += 1;
            diff[i + d2[i] + 1] -= 1;
        }
    }
    ll cur = 0;
    cntEnd[0] = 0;
    for (int e = 1; e <= len; e++) {
        cur += diff[e];
        cntEnd[e] = cur;
    }
    preEnd[0] = 0;
    for (int k = 1; k <= len + 1; k++) preEnd[k] = preEnd[k - 1] + cntEnd[k - 1] + 1;
}

// 对串 s 建双底数滚动哈希,h[k][i] 表示 s 前 i 个字符的哈希值
void build_hash(unsigned long long h[2][MAXN], const char *s, int len) {
    for (int k = 0; k < 2; k++) {
        unsigned long long base = (k == 0 ? BASE1 : BASE2);
        h[k][0] = 0;
        for (int i = 0; i < len; i++) h[k][i + 1] = h[k][i] * base + (unsigned char)s[i];
    }
}

// 两套底数的幂表,长度到 max(|A|,|B|)
void build_power(int len) {
    for (int k = 0; k < 2; k++) {
        unsigned long long base = (k == 0 ? BASE1 : BASE2);
        power[k][0] = 1;
        for (int i = 1; i <= len; i++) power[k][i] = power[k][i - 1] * base;
    }
}

// 哈希判等:A[l..l+len-1] 与 rev(B)[r..r+len-1] 是否相同(两套底数都过才算相同)
bool same_hash(int l, int r, int len) {
    for (int k = 0; k < 2; k++) {
        unsigned long long x = hashA[k][l + len] - hashA[k][l] * power[k][len];
        unsigned long long y = hashR[k][r + len] - hashR[k][r] * power[k][len];
        if (x != y) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string dtype;
    if (!(cin >> dtype)) return 0; // 第一行是数据类型,本题的算法与它无关
    cin >> strA >> strB;
    n = strlen(strA);
    m = strlen(strB);
    for (int i = 0; i < m; i++) strR[i] = strB[m - 1 - i]; // rev(B)

    build_start(strA, n);
    build_end(strB, m);
    build_power(max(n, m));
    build_hash(hashA, strA, n);
    build_hash(hashR, strR, m);

    int q;
    cin >> q;
    string out;
    out.reserve((size_t)q * 16);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        int st = x - 1;        // A_x 在 A 中的起点(0-based)
        int L = m - y + 1;     // B_y 的长度
        int limit = min(n - st, L); // P 的上界:两个串都要取得到这么长的前缀

        // 二分求 P = LCP(A[st..], rev(B)[y-1..])
        int lo = 0, hi = limit;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (same_hash(st, y - 1, mid)) lo = mid;
            else hi = mid - 1;
        }

        ll ans = (preEnd[L] - preEnd[L - lo]) + (preStart[x + lo] - preStart[x]);
        out += to_string(ans);
        out += '\n';
    }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

复杂度

  • 时间:Manacher 与哈希建表各 O(n+m)O(n+m),两趟差分前缀和 O(n+m)O(n+m);每组询问一次二分 O(log⁡min⁡(n,m))O(\log\min(n,m))。总计 O(n+m+Qlog⁡min⁡(n,m))O\bigl(n+m+Q\log\min(n,m)\bigr)。
  • 空间:d1,d2d_1,d_2、哈希与幂表、四个计数/前缀和数组都是 O(n+m)O(n+m);C++ 侧用全局静态数组, 上限开 8×105+58\times 10^5+5。
  • 与 C++ 解法的关系:main.py 是同一算法,只是把两套底数压成一套(Python 大整数天然 2642^{64} 掩码)、把 diff 数组写成列表推导 + accumulate。Python 在大数据点上会明显偏慢, 本题的正式提交以 main.cpp 为准。

总结

  • 先分类再计数:把 (p,q)(p,q) 按 p⩽qp\leqslant q 与 p>qp>q 切开,每一类的"匹配"条件都退化成 单一的 p⩽Pp\leqslant P,剩下的是纯回文计数,两行和式就读完了。
  • 回文计数的正确抽象是"端点出现次数":不是我需要哪些回文串,而是"位置 ii 作为回文前缀 起点出现多少次";Manacher 的每个中心给出一个连续的端点区间,差分数组正好把这层 区间加摊平成 O(n)O(n)。
  • 多出来的 +1+1 不是凑出来的:q=pq=p 时中间段为空,而空串是回文,所以每个 pp 都凭空多一种, 这就是 cntB[e]+1\mathrm{cntB}[e]+1 里那个 11 的来源;漏掉它样例 1 会得到 1111 而不是 1616。
  • 动态量交给哈希二分:PP 随询问变化且没有单调性,用哈希 + 二分是最省事的选择, 双底数把碰撞风险压到可忽略。