把 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
形式化题目
给定两个串
是 的非空前缀, 是 的非空后缀; - 把
与 拼接后得到的串 是回文串。
有
把下标换成 0 起会好写很多:令
则
数据分三档类型:
正解
思路
先固定一个查询看结构。 设
| 匹配段 | 中间段 | 计数 | |
|---|---|---|---|
| 每个 |
|||
| 每个 |
两类的第一个条件都只是"
为什么中间段回文就够了? 以
两个回文计数表。 定义
那么
第一条和式的
两张表怎么 O(n) 求。
边界处理。
代码
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++ 版(同一算法):
/**
* 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 与哈希建表各
,两趟差分前缀和 ;每组询问一次二分 。总计 。 - 空间:
、哈希与幂表、四个计数/前缀和数组都是 ;C++ 侧用全局静态数组, 上限开 。 - 与 C++ 解法的关系:
main.py是同一算法,只是把两套底数压成一套(Python 大整数天然掩码)、把 diff数组写成列表推导 +accumulate。Python 在大数据点上会明显偏慢, 本题的正式提交以main.cpp为准。
总结
- 先分类再计数:把
按 与 切开,每一类的"匹配"条件都退化成 单一的 ,剩下的是纯回文计数,两行和式就读完了。 - 回文计数的正确抽象是"端点出现次数":不是我需要哪些回文串,而是"位置
作为回文前缀 起点出现多少次";Manacher 的每个中心给出一个连续的端点区间,差分数组正好把这层 区间加摊平成 。 - 多出来的
不是凑出来的: 时中间段为空,而空串是回文,所以每个 都凭空多一种, 这就是 里那个 的来源;漏掉它样例 1 会得到 而不是 。 - 动态量交给哈希二分:
随询问变化且没有单调性,用哈希 + 二分是最省事的选择, 双底数把碰撞风险压到可忽略。