字符串哈希
题目重述
给定一个仅含小写英文字母的字符串 ,将其划分为若干非空子串 ,满足
称该划分为 palindromic,当且仅当把每个 看作一个原子后,序列 本身是回文的,即
要求输出最大的可能 。
输入第一行为测试组数 ,随后 行每行一个字符串 。约束为 ,。
样例:
| 输入 | 输出 |
|---|---|
bonobo |
|
deleted |
|
racecar |
|
racecars |
关键观察
观察 1. 在任意 palindromic 划分中,最左侧的 chunk 与最右侧的 chunk 必须完全相同;同理,第 个 chunk 必须等于倒数第 个 chunk。
证明. 由 palindromic 划分的定义,chunk 序列作为原子序列是回文,故对称位置上的原子相等。
观察 2. 为最大化 chunk 数量,应反复取当前字符串两端能够匹配的最短相等前后缀作为最外层 chunk,然后对剩余中间子串继续该过程。
证明. 设当前子串为 ,某合法划分的最外层 chunk 长度为 。若存在更短的可匹配长度 ,将最外层换成长度为 的相等前后缀后,中间剩余子串长度从 增加到 ,而划分出的外层 chunk 数量不变。更长的中间子串至多不会减少其内部可划分出的 chunk 数,因此总 chunk 数不会变少。
观察 3. 若能在 时间内判断任意两个子串是否相等,则上述贪心过程可在 总时间内完成。
解析
进制视角下的字符串哈希
将每个字符映射为一个数字,例如 'a' \to 1, 'b' \to 2, \dots, 'z' \to 26。字符串 可视为一个以 为基数的“大数”:
该值通常过大,因此对其取模 :
预处理前缀哈希:
同时预处理基数的幂次 。则任意区间 的哈希值可如下截取:
这正类似于从一个大数中截取连续若干位:先将前缀 左移到高位,再整体减去,剩余部分即为区间 对应的数值。
贪心双指针过程
维护左指针 与右指针 ,以及当前待匹配长度 :
len = 0, cnt = 0for 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循环结束后,若 或 为奇数,则中间剩余字符单独构成一个 chunk,故 。
正确性
由观察 2,每次取最短匹配外层不会使答案变差;由观察 1,任何合法划分都必须遵守外层 chunk 相等的约束。因此上述贪心得到全局最优解。哈希仅用于 比较子串相等性,不影响贪心正确性。
复杂度分析
预处理前缀哈希与幂次需要 时间与 空间。双指针扫描过程需要 时间。因此每组测试数据的时空复杂度均为 ,满足 的约束。
代码
#include <bits/stdc++.h>#include <iomanip>#include <utility>#define ll long long#define N 200005using 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;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时