1092 字
5 分钟
字符串哈希

字符串哈希#

题目重述#

给定一个仅含小写英文字母的字符串 ss,将其划分为若干非空子串 a1,a2,…,ada_1,a_2,\dots,a_d,满足

s=a1+a2+⋯+ad.s = a_1 + a_2 + \dots + a_d .

称该划分为 palindromic,当且仅当把每个 aia_i 看作一个原子后,序列 a1,a2,…,ada_1,a_2,\dots,a_d 本身是回文的,即

ai=ad+1−i,1≤i≤d.a_i = a_{d+1-i}, \qquad 1 \le i \le d .

要求输出最大的可能 dd。

输入第一行为测试组数 tt,随后 tt 行每行一个字符串 ss。约束为 1≤t≤101 \le t \le 10,1≤∣s∣≤1061 \le |s| \le 10^6。

样例:

输入 输出
bonobo 33
deleted 55
racecar 77
racecars 11

关键观察#

观察 1. 在任意 palindromic 划分中,最左侧的 chunk 与最右侧的 chunk 必须完全相同;同理,第 ii 个 chunk 必须等于倒数第 ii 个 chunk。

证明. 由 palindromic 划分的定义,chunk 序列作为原子序列是回文,故对称位置上的原子相等。■\blacksquare

观察 2. 为最大化 chunk 数量,应反复取当前字符串两端能够匹配的最短相等前后缀作为最外层 chunk,然后对剩余中间子串继续该过程。

证明. 设当前子串为 s[l…r]s[l\dots r],某合法划分的最外层 chunk 长度为 LL。若存在更短的可匹配长度 L′<LL' < L,将最外层换成长度为 L′L' 的相等前后缀后,中间剩余子串长度从 r−l+1−2Lr-l+1-2L 增加到 r−l+1−2L′r-l+1-2L',而划分出的外层 chunk 数量不变。更长的中间子串至多不会减少其内部可划分出的 chunk 数,因此总 chunk 数不会变少。■\blacksquare

观察 3. 若能在 O(1)O(1) 时间内判断任意两个子串是否相等,则上述贪心过程可在 O(n)O(n) 总时间内完成。

解析#

进制视角下的字符串哈希#

将每个字符映射为一个数字,例如 'a' \to 1, 'b' \to 2, \dots, 'z' \to 26。字符串 s[1…k]s[1\dots k] 可视为一个以 BB 为基数的“大数”:

H(s[1…k])=s1⋅Bk−1+s2⋅Bk−2+⋯+sk−1⋅B+sk.H(s[1\dots k]) = s_1 \cdot B^{k-1} + s_2 \cdot B^{k-2} + \dots + s_{k-1} \cdot B + s_k .

该值通常过大,因此对其取模 MM:

H(s[1…k])(modM).H(s[1\dots k]) \pmod M .

预处理前缀哈希:

pre[i]=(pre[i−1]⋅B+si) mod M.pre[i] = \bigl(pre[i-1] \cdot B + s_i\bigr) \bmod M .

同时预处理基数的幂次 pw[i]=Bi mod Mpw[i] = B^i \bmod M。则任意区间 [l,r][l,r] 的哈希值可如下截取:

H(s[l…r])=(pre[r]−pre[l−1]⋅pw[r−l+1]) mod M.H(s[l\dots r]) = \bigl(pre[r] - pre[l-1] \cdot pw[r-l+1]\bigr) \bmod M .

这正类似于从一个大数中截取连续若干位:先将前缀 [1,l−1][1,l-1] 左移到高位,再整体减去,剩余部分即为区间 [l,r][l,r] 对应的数值。

贪心双指针过程#

维护左指针 ll 与右指针 rr,以及当前待匹配长度 lenlen:

len = 0, cnt = 0
for l = 1, r = n; l <= n/2; ++l, --r:
++len
if H(l-len+1, l) == H(r, r+len-1):
cnt += 2
len = 0

循环结束后,若 len>0len > 0 或 nn 为奇数,则中间剩余字符单独构成一个 chunk,故 cnt←cnt+1cnt \leftarrow cnt + 1。

正确性#

由观察 2,每次取最短匹配外层不会使答案变差;由观察 1,任何合法划分都必须遵守外层 chunk 相等的约束。因此上述贪心得到全局最优解。哈希仅用于 O(1)O(1) 比较子串相等性,不影响贪心正确性。

复杂度分析#

预处理前缀哈希与幂次需要 O(n)O(n) 时间与 O(n)O(n) 空间。双指针扫描过程需要 O(n)O(n) 时间。因此每组测试数据的时空复杂度均为 O(n)O(n),满足 ∣s∣≤106|s| \le 10^6 的约束。

代码#

#include <bits/stdc++.h>
#include <iomanip>
#include <utility>
#define ll long long
#define N 200005
using namespace std;
ll ans;
ll n, m, k;
ll t;
#define pr pair<ll, ll>
const ll B = 337;
const ll M = 1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--) {
auto solve = [&]() {
string s;
cin >> s;
n = s.length();
vector<ll> pre(n + 5, 0);
vector<ll> p(n + 5, 0);
auto init = [&]() {
p[0] = 1;
for (int i = 1; i <= n; i++) {
pre[i] = (pre[i - 1] * B + s[i]) % M;
p[i] = p[i - 1] * B % M;
}
};
s = '0' + s;
init();
int mid = n / 2;
ll len = 0;
ll cnt = 0;
auto cal = [&](int l, int r) {
return (pre[r] - pre[l - 1] * p[r - l + 1] % M + M) % M;
};
for (int l = 1, r = n; l <= mid; l++, r--) {
len++;
if (cal(l - len + 1, l) == cal(r, r + len - 1)) {
len = 0;
cnt += 2;
}
}
if (len || (n % 2))
cnt++;
cout << cnt << '\n';
};
solve();
}
return 0;
}
字符串哈希
https://sanzenin.top/posts/obsidian/字符串哈希/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取