「v4」0x20 字符串
同步于 2026-11-11,花费 14,451,581 tok。
0x21 字符串 I
哈希
字符串哈希
字符串哈希:字符串哈希要求数据有序。将字符串的元素通过某种不具有交换律的运算结合(例如字符串拼接,矩阵乘法 …)。
通常将字符串 s 视为一个 \mathrm{base} 进制数,即
其中模数 M 尽量为大质数,并且尽量对两个大质数模数 M_1, M_2 各求一次哈希(双哈希)
静态字符串区间哈希:
动态字符串区间哈希:区间哈希值可以合并。设左右两个区间的长度与哈希值分别为 (l_1, h_1), (l_2, h_2),将它们拼接形成大区间的长度与哈希值为
可以使用线段树动态维护。
卡自然溢出哈希(Hash Killer I):
\mathrm{base} 为偶数:此时 \mathrm{base}^{64} \equiv 0 \pmod{2^{64}}。所以两个长度 > 64 且后 64 位相同但不完全相同的字符串就会哈希冲突。
\mathrm{base} 为奇数:使用 Thue Morse 序列攻击。对于二进制串 s,设 \overline{s} 表示 s 按位取反后得到的串。
Thue Morse 序列:t_0 = \mathtt{0},t_i = t_{i - 1} + \overline{t_{i - 1}}。此时
记 h_i = f(t_i) - f(\overline{t_i}),有 h_i = \left(\mathrm{base}^{2^{i - 1}} - 1\right)h_{i - 1}。由于
其中每一项都是偶数,所以 2^i \mid \mathrm{base}^{2^{i - 1}} - 1。于是 2^{\frac{i(i + 1)}{2}} \mid h_i,因此 t_{11} 与 \overline{t_{11}} 就会哈希冲突。
Thue Morse 序列的规律:第 x (x \geq 0) 位上的值等于 \mathrm{popcount}(x) \bmod 2。
卡大质数哈希(Hash Killer II):使用生日悖论攻击。
集合哈希
集合哈希:集合哈希要求数据无序。将集合的元素通过某种映射规则转化后,再通过某种具有交换律的运算结合。
可用的映射规则:用来打乱原来可能有的某些性质。
- 查表映射:给原数值 x 随机赋一个新数值 c_x 并存入表中。
可用的结合方式:
-
使用加法结合:
-
使用异或结合(异或哈希):
此时出现偶数次元素无贡献,出现奇数次元素只贡献一次。
异或哈希判完全平方数:定义完全异或性函数 f,对于任意正整数 x, y 都有 f(xy) = f(x) \oplus f(y)。先对 1 \sim n 进行一次线性筛。给其中的所有质数 p 对应的 f(p) 赋一个范围较大的随机数,其余合数的 f 值通过线性筛得出。
此时 x 为完全平方数,极大概率等价于 f(x) = 0。
当待判断的数可以表示为若干个 [1, n] 范围内整数的乘积时,就可以根据这些数的 f 函数异或和求出该数的 f 函数,从而快速判断其是否为完全平方数。
kmp
字符串的 border:对字符串 s 与整数 0 \leq r < |s|,若 s 长度为 r 的前缀与后缀相等,则称 s 长度为 r 的前缀为 s 的 border。
字符串的周期:对字符串 s 与整数 1 \leq p \leq |s|,若对于任意 i \in [1, |s| - p] 均有 s_i = s_{i + p},则称 p 为 s 的周期。特别地,若 p 整除 |s|,则称 p 为 s 的整周期。
相当于 s[1 : n - p] = s[p + 1 : n],所以 s 有长度为 r 的 border \iff |s| - r 是 s 的周期。
kmp:记 \mathrm{next}_i 表示字符串 s[1 : i] 的最长 border 的长度。
利用 border 的 border 还是原串 border 的性质,可以 \mathcal{O}(n) 求解前缀函数。
进一步,s[1 : i] 的所有 border 为 \mathrm{next}_i, \mathrm{next}_{\mathrm{next}_i}, \dots
0x21 kmp.cpp:
// net[i]:s[1:i] 真前缀与真后缀匹配的最大长度(s[1:i] 的 border)
auto kmp(const auto &s) {
int n = s.size() - 1; // s 下标从 1 开始
std::vector<int> net(n + 1);
net[1] = 0;
for (int i = 2, j = 0; i <= n; i ++) {
while (j > 0 && s[j + 1] != s[i]) j = net[j];
if (s[j + 1] == s[i]) j ++;
net[i] = j;
}
return net;
}
// f[i]:t[1:i] 后缀与 s 前缀匹配的最大长度
auto kmp_match(const auto &s, const auto &t, const auto &net) {
int n = s.size() - 1, m = t.size() - 1; // s, t 下标从 1 开始
std::vector<int> f(m + 1);
for (int i = 1, j = 0; i <= m; i ++) {
while (j > 0 && (j == n || s[j + 1] != t[i])) j = net[j];
if (s[j + 1] == t[i]) j ++;
f[i] = j;
}
return f;
}border 理论
弱周期引理:若 p, q 是 s 的周期且 p + q \leq n,则 \gcd(p, q) 也是 s 的周期。
证明:不妨设 p > q,下面证明 p - q 也是 s 的周期。
- 当 i \leq q 时,s_i = s_{i + p} = s_{i + p - q}。
- 当 i > q 时,s_i = s_{i - q} = s_{i + p - q}。
所以 p - q 也是 s 的周期,运用辗转相除法可知 \gcd(p, q) 也是 s 的周期。
周期引理:若 p, q 是 s 的周期且 p + q - \gcd(p, q) \leq n,则 \gcd(p, q) 也是 s 的周期。
长 border 结构:s 的所有长度 \geq \left\lfloor\frac{n}{2}\right\rfloor 的 border,它们与 n 共同构成一个等差数列,公差为 s 的最小周期。
证明:设 n - p, n - q (p, q \leq \left\lceil \frac{n}{2} \right\rceil) 是两个不同的 border,其中 n - p 是最大的 border。
已知 p, q 是 s 的周期,由于 p + q \leq n,可知 \gcd(p, q) 也是 s 的周期。由于 n - p 是最大 border,所以 p 是最小周期。结合两个条件可得 \gcd(p, q) = p,即 p \mid q。同时,周期的整数倍也一定是周期。
综上,s 的所有长度 \geq \left\lfloor\frac{n}{2}\right\rfloor 的 border 与 n 共同构成一个公差为 p(最小周期)的等差数列。
短周期结构:s 的所有长度 \leq \left\lceil \frac{n}{2} \right\rceil 的周期,都是 s 最小周期的倍数。
证明同「长 border 结构」。
字符串 border 结构:s 的所有 border 可以被划分成至多 \left\lceil \log_2 n \right\rceil 个等差数列。
进一步,每个等差数列都具有一定的周期性。同一个等差数列里的字符串,都可以被表示成
或
其中 W, A, B 均为字符串。
证明:设 [2^i, 2^{i + 1}) 中最大的 border 为 p,那么段内的其余 border 都是 s[1 : p] 的 border,且长度 \geq \left\lfloor \frac{p}{2} \right\rfloor,由「长 border 结构」可知段内构成一个等差数列。
推论:s 的所有公差 \geq d 的 border 的等差数列总大小是 \mathcal{O}\left( \frac{n}{d} \right) 的。
Misc:
- 若 s 在 t 中的某两个匹配 s_1, s_2 有重合,且起始位置相差 d,则 d 均为 s 与 s_1 \cup s_2(两个匹配区间并)的周期。
- 若 |s| \geq \frac{|t|}{2},则 s 在 t 中的匹配起始位置形成等差数列。若该等差数列至少有 3 项,则公差为 s 的最小周期 \mathrm{per}(s)。
Z Algorithm
Z Algorithm:记 Z_i 表示字符串 s 与 s[i : n] 的最长公共前缀(LCP)长度。在某些情况下,可能会记 Z_1 = 0。
考虑从前向后扫。维护一个右端点最靠右,且与 s 的前缀匹配的子串 s[l : r]。
-
若 i \leq r,则
-
若 i > r,则
在当前 Z_i 的基础上不断尝试扩展。
注意到单次枚举的次数为 \max\{l + Z_l - 1\} 的增量,时间复杂度 \mathcal{O}(n)。
0x21 Z-Algorithm.cpp:
// Z[i]:lcp(s, s[i:n])
auto Zalgo(const auto &s) {
int n = s.size() - 1; // s 下标从 1 开始
std::vector<int> Z(n + 1);
Z[1] = n;
for (int i = 2, l = 0, r = 0; i <= n; i ++) {
int &x = Z[i] = i <= r ? std::min(Z[i - l + 1], r - i + 1) : 0;
while (i + x <= n && s[1 + x] == s[i + x]) {
x ++;
}
if (i + x - 1 > r) {
l = i, r = i + x - 1;
}
}
return Z;
}
// p[i]:lcp(s, t[i:m])
auto Zalgo_match(const auto &s, const auto &t, const auto &Z) {
int n = s.size() - 1, m = t.size() - 1; // s, t 下标从 1 开始
std::vector<int> p(m + 1);
for (int i = 1, l = 0, r = 0; i <= m; i ++) {
int &x = p[i] = i <= r ? std::min(Z[i - l + 1], r - i + 1) : 0;
while (1 + x <= n && i + x <= m && s[1 + x] == t[i + x]) {
x ++;
}
if (i + x - 1 > r) {
l = i, r = i + x - 1;
}
}
return p;
}manacher
奇偶回文串的处理:回文串按照长度分成奇偶两类,奇回文串的对称轴处于一个字符上,偶回文串的对称轴处于两个相邻字符的中间。
可以在一个字符串的首尾以及所有的相邻两字符之间,插入一个原串中从未出现的字符(例如 #, $, ^)。
这样原串中的每一个回文串,都可以对应到新串中的一个两端都是分隔符的奇回文串。
manacher:记 p_i 表示以位置 i 为中心的最长回文子串的半径(含中心)。
考虑从前向后扫。维护一个右端点最靠右的回文子串,不妨记该回文串的中心为 k。
-
若 i \leq k + p_k - 1,则
-
若 i > k + p_k - 1,则
在当前 p_i 的基础上不断尝试扩展。
注意到单次枚举的次数为 \max\{k + p_k - 1\} 的增量,时间复杂度 \mathcal{O}(n)。
0x21 manacher.cpp:
// 转化为形如 #a#b#c# 的字符串
auto manacher_init(const std::string &s) {
std::string t = " #";
for (char ch : s) {
t += ch, t += "#";
}
return t;
}
// p[i]:区间 [i - p[i] + 1, i + p[i] - 1] 回文
auto manacher(const auto &s) {
int n = s.size() - 1; // s 下标从 1 开始
std::vector<int> p(n + 1);
for (int i = 1, mid = 0, r = 1; i <= n; i ++) {
int &x = p[i] = i < r ? std::min(r - i, p[mid - i]) : 0;
while (i - x > 0 && i + x <= n && s[i - x] == s[i + x]) {
x ++;
}
if (i + x > r) {
mid = i * 2, r = i + x;
}
}
return p;
}
// 以位置 i 为回文中心的最长回文子串,在原串中的长度为 p[i] - 1(转换成 #a#b#c# 形式后)
// 判断原串区间 [l, r] 是否回文:p[l + r] - 1 >= r - l + 1(转换成 #a#b#c# 形式后)0x21 manacher(奇偶分开考虑).cpp:
// p[i]:区间 [i - p[i] + 1, i + p[i] - !is_even] 回文,奇偶分开考虑
auto manacher(const auto &s, int is_even) {
int n = s.size() - 1; // s 下标从 1 开始
std::vector<int> p(n + 1);
for (int i = 1, mid = 0, r = 1; i <= n - is_even; i ++) {
int &x = p[i] = i < r ? std::min(r - i, p[mid - i]) : 0;
while (i - x > 0 && i + x + is_even <= n && s[i - x] == s[i + x + is_even]) {
x ++;
}
if (i + x > r) {
mid = i * 2, r = i + x;
}
}
return p;
}反回文串:对于长度为 n 的字符串 s,若对于任意 i \in [1, n] 均有 s_i \neq s_{n - i + 1},则称 s 为反回文串。
01 串的反 manacher:相当于对于每两个相邻字符的中间,求以该位置为中心的最长反回文子串的半径。注意我们只需要考虑长度为偶数的串。
当字符集大小为 2 时,考虑形如 ABCD 的字符串,若已知 A \neq B, A \neq D, B \neq C,可以推出 C\neq D,所以 manacher 的对称复用逻辑还是正确的。但是字符集大小超过 2 的时候,上述推理就不成立了。
具体实现时,只需要将 manacher 偶回文串指针扩展过程中的 == 改成 != 即可。
Lyndon 分解
Lyndon 串:对于字符串 s,若 s 的字典序小于 s 的所有非空真后缀,则称 s 为 Lyndon 串。
等价定义:
- 字符串 s 的字典序严格小于 s 的其他循环移位。
- 对字符串 s 的任意非空分解 s = uv,都有 u < v。
- 对字符串 s 的任意非空分解 s = uv,都有 uv < vu。
Lyndon 串的拼接性质:
- 若字符串 u, v 均为 Lyndon 串并且 u < v,则 uv 为 Lyndon 串,且 u < uv < v。
- 若字符串 u, v 均为 Lyndon 串并且 u < v,则对于任意正整数 a, b,均有 u^av^b 为 Lyndon 串,且 u < u^av^b < v。
- 字符串 s (|s| \geq 2) 是 Lyndon 串,当且仅当 s = uv (|u| > 0, |v| > 0, \boldsymbol{u < v}) 并且 u, v 均为 Lyndon 串。
Lyndon 串的简单性质:
- Lyndon 串不存在非空 border。
- 截取 Lyndon 串的某个前缀,将其末字符增大,结果仍是 Lyndon 串(截出的前缀本身不必是 Lyndon 串)。
- 若字符串 s_1, s_2 满足 s_1 是 Lyndon 串且 s_1 > s_2,则 s_1 > s_2^2。
Lyndon 分解:将字符串 s 分解为 w_1w_2\dots w_k,其中所有的 w_i 均为 Lyndon 串,且满足 w_1 \geq w_2 \geq \dots \geq w_k。
Lyndon 分解的性质:
- Lyndon 分解存在且唯一。
- 字符串 s 是 Lyndon 串当且仅当 k = 1。
- 第一块 w_1:是原串最长的 Lyndon 前缀。
- 最后一块 w_k:是原串最长的 Lyndon 后缀,也是原串字典序最小的非空后缀。
Lyndon 分解(duval):维护三个指针 i, j, k,将字符串分成三个部分:
- s[1 : i - 1]:这部分的 Lyndon 分解已完成。
- s[i : j - 1]:这部分可以被表示为 w^c + v,其中 w 是一个 Lyndon 串,v 是 w 的可空真前缀。
- s[j : n]:这部分还未处理,当前考虑的是位置 j。
其中 k = j - |w|,那么 s_k 表示继续循环下去时,位置 j 应当出现的字符。
接下来有三种情况:
- s_k = s_j:可以将 w 继续循环下去,令 k \gets k + 1,j \gets j + 1。
- s_k < s_j:此时 w^c + v + s_j 本身是一个 Lyndon 串,将其作为新的 w,令 k \gets i,j \gets j + 1。
- s_k > s_j:将当前的 c 个 w 依次加入 Lyndon 分解,然后从 v 的开头重新扫描。
每一轮 j 扫描的长度,不超过 i 前进长度的两倍。时间复杂度 \mathcal{O}(n)。
0x21 duval.cpp:
// Lyndon 分解
auto duval(const auto &s) {
int n = s.size() - 1; // s 下标从 1 开始
std::vector<int> res;
for (int i = 1; i <= n;) {
int j = i + 1, k = i;
for (; j <= n && s[k] <= s[j]; j ++) {
if (s[k] < s[j]) {
k = i;
} else {
k ++;
}
}
for (; i <= k; i += j - k) {
res.push_back(i);
}
}
return res;
}标准分解:对于 Lyndon 串 s (|s| \geq 2),记 s 的最长 Lyndon 真后缀为 v,此时 s = uv,记 (u, v) 为 s 的标准分解。
最小表示法
循环同构:若长度为 n 的字符串 s,可以选择一个起始位置 i (1 \leq i \leq n),使得 s[i : n] + s[1 : i - 1] = t,则称 s, t 循环同构。
最小表示法:字符串 s 的最小表示法,为与 s 循环同构的所有字符串中,字典序最小的字符串。
对于两个不同的起始位置 i, j,已知它们的前 k 位相同。考虑继续比较下一位:
- 若 s_{(i + k) \bmod n} > s_{(j + k) \bmod n},可以发现区间 [i, i + k] 内的起始位置都不能成为答案,因为对于起始位置 i + p (p \in [0, k]) 来说,起始位置 j + p 一定更优。所以此时可以跳过区间 [i, i + k] 的起始位置,令 i \gets i + k + 1,k \gets 0。
- 若 s_{(i + k) \bmod n} < s_{(j + k) \bmod n} 也是同理,跳过区间 [j, j + k] 的起始位置,令 j \gets j + k + 1,k \gets 0。
- 若 s_{(i + k) \bmod n} = s_{(j + k) \bmod n},令 k \gets k + 1,然后继续比较。
在跳转的过程中,若两个起始位置 i, j 相同,则任选一个加一。最终 \min(i, j) 即为最优的起始位置。
时间复杂度 \mathcal{O}(n)。
0x21 最小表示法.cpp:
// 最小表示法
// std::rotate(s.begin(), s.begin() + minrep(s), s.end());
int minrep(const auto &s) {
int n = s.size(), k = 0, i = 0, j = 1; // s 下标从 0 开始
while (k < n && i < n && j < n) {
int d = s[(i + k) % n] - s[(j + k) % n];
if (d == 0) {
k ++;
} else {
(d > 0 ? i : j) += k + 1;
if (i == j) i ++;
k = 0;
}
}
return std::min(i, j);
}带通配符的字符串匹配
0x22 字符串 II
Trie
trie:trie 是一个纯正的自动机,形态是树。
- 一个起点,若干终点。
- 多模式串的所有前缀,与 trie 上的所有状态一一对应。
- trie 主要考虑一种转移边:表示在当前状态所表示的串后面加一个字符。
01 trie:
- 01 trie 支持可持久化,可以作为 01 trie 的前缀和来使用。
- 01 trie 支持合并:
- 01 trie 单次合并复杂度,取决于两棵 01 trie 的交集大小。
- 01 trie 合并总复杂度,取决于所有 01 trie 的节点总数。
- 01 trie 支持可持久化合并,需要在合并时新建节点。
0x22 01 trie.cpp:
// 01 trie
namespace trie {
const int pond = 10001000; // 内存池大小,需要根据实际问题调整
int nodeCount;
struct node {
int trans[2];
int cnt;
#define lc trans[0]
#define rc trans[1]
} t[pond];
int newnode() {
int p = ++ nodeCount;
t[p].lc = t[p].rc = t[p].cnt = 0;
return p;
}
void insert(int &p, int d, int x) {
if (!p) p = newnode();
t[p].cnt ++;
if (d < 0) return;
int v = x >> d & 1;
insert(t[p].trans[v], d - 1, x);
}
int merge(int p, int q) {
if (!p || !q) return p ^ q;
t[p].cnt += t[q].cnt;
t[p].lc = merge(t[p].lc, t[q].lc);
t[p].rc = merge(t[p].rc, t[q].rc);
return p;
}
// 可持久化 01 trie 合并
// int merge(int p, int q) {
// if (!p || !q) return p ^ q;
// int u = newnode();
// t[u].cnt = t[p].cnt + t[q].cnt;
// t[u].lc = merge(t[p].lc, t[q].lc);
// t[u].rc = merge(t[p].rc, t[q].rc);
// return u;
// }
}0x22 可持久化 01 trie.cpp:
// 可持久化 01 trie
namespace trie {
const int pond = 10001000; // 内存池大小,需要根据实际问题调整
int nodeCount;
struct node {
int trans[2];
int cnt;
} t[pond];
void insert(int &p, int q, int d, int x) {
p = ++ nodeCount, t[p] = t[q], t[p].cnt ++;
if (d < 0) return;
int v = x >> d & 1;
insert(t[p].trans[v], t[q].trans[v], d - 1, x);
}
}01 trie 查询与 x 异或的最大值:从高位到低位贪心,有异走异,无异走同。
01 trie 查询与 x 异或的第 k 大值:从高位到低位
- 设当前考虑到第 i 位,设 x 的异位有 \mathrm{cnt} 个数。
- 若 k \leq \mathrm{cnt},则查询 x 的异位中,与 x 异或的第 k 大值。
- 若 k > \mathrm{cnt},则查询 x 的同位中,与 x 异或的第 k - \mathrm{cnt} 大值。
01 trie 查询与 x 异或 \geq k 的信息:从高位到低位
- 设当前考虑到第 i 位:
- 若 k 的第 i 位为 1,直接走 x 的异位。
- 若 k 的第 i 位为 0,统计 x 的异位的贡献,然后走 x 的同位。
- 考虑完所有位之后,统计当前叶子节点的贡献。
01 trie 全局异或 x:从高位到低位,运用懒标记。
设当前考虑到第 i 位,若懒标记的第 i 位为 1,则交换左右儿子。
01 trie 维护集合异或和,支持插入、删除、全局 +1:从低位到高位
- 额外维护:
- \mathrm{cnt}:当前状态的子树内插入数的个数。
- \mathrm{xr}:当前状态的子树内的异或和。
- 插入、删除:递归操作即可。
- 全局 +1:交换当前节点的左右儿子,然后进入 0 转移边(未交换前是 1 转移边)的儿子进行递归交换。
(因为二进制下 +1,相当于是从低位到高位找到第一个 0 将其改为 1,然后将前面的 1 都改为 0)
0x22 01 trie 维护集合异或和.cpp:
// 01 trie 维护集合异或和
namespace trie {
const int pond = 10001000; // 内存池大小,需要根据实际问题调整
int nodeCount;
struct node {
int trans[2];
int cnt;
int xr;
#define lc trans[0]
#define rc trans[1]
} t[pond];
int newnode() {
int p = ++ nodeCount;
t[p].lc = t[p].rc = t[p].cnt = t[p].xr = 0;
return p;
}
void upd(int p) {
t[p].cnt = t[t[p].lc].cnt + t[t[p].rc].cnt;
t[p].xr = (t[t[p].lc].xr << 1) ^ (t[t[p].rc].xr << 1) ^ (t[t[p].rc].cnt & 1);
}
void insert(int &p, int d, int x, int y) {
if (!p) p = newnode();
if (d == 31) {
t[p].cnt += y;
return;
}
int v = x >> d & 1;
insert(t[p].trans[v], d + 1, x, y);
upd(p);
}
void addone(int p) {
std::swap(t[p].lc, t[p].rc);
if (t[p].lc) addone(t[p].lc);
upd(p);
}
}AC 自动机
AC 自动机:AC 自动机是一个状态自动机,形态是 trie。
- 一个起点,若干终点。
- 多模式串的所有前缀,与 AC 自动机上的所有状态一一对应。
- AC 自动机主要考虑两种边:
- 普通转移边:表示在当前状态所表示的串后面加一个字符。
- 失配指针 fail:表示当前状态所表示的串的最长匹配后缀。这类边构成一棵树,称作 fail 树。
trie 图:将原来 trie 中不存在的转移边 \delta(p, c) 指向 \delta(\mathrm{fail}_p, c)。本质上是路径压缩。
trie 图的普通转移边:从字符串 s 指向 s' + c,其中 s' 为 s 中满足 s' + c 存在的最长后缀。
0x22 AC 自动机.cpp:
// AC 自动机
namespace AC {
const int SIZE = 1000100; // 多模式串长度总和,需要根据实际问题调整
int nodeCount;
struct node {
int trans[26];
int fail;
} t[SIZE];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].fail = 0;
return p;
}
void init() {
nodeCount = 0, newnode(); // 根节点为 1
}
void insert(const std::string &s) {
int p = 1;
for (char ch : s) {
int v = ch - 'a';
if (!t[p].trans[v]) t[p].trans[v] = newnode();
p = t[p].trans[v];
}
}
void build_fail() {
for (int i = 0; i < 26; i ++) t[0].trans[i] = 1;
t[1].fail = 0;
std::queue<int> q;
q.push(1);
while (q.size()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i ++) {
if (t[u].trans[i]) {
t[t[u].trans[i]].fail = t[t[u].fail].trans[i];
q.push(t[u].trans[i]);
} else {
t[u].trans[i] = t[t[u].fail].trans[i];
}
}
}
}
}AC 自动机(大字符集):当字符集很大时,需要用到 std::map 与可持久化数组建立 trie 图。
0x22 AC 自动机(大字符集).cpp:
// 可持久化数组
namespace SGT {
const int pond = 10001000; // 内存池大小,需要根据实际问题调整
int nodeCount;
struct node {
int lc, rc;
int val;
} t[pond];
void init() {
nodeCount = 0, t[0].val = 1;
}
void insert(int &p, int q, int l, int r, int x, int y) {
p = ++ nodeCount, t[p] = t[q];
if (l == r) { t[p].val = y; return; }
int mid = (l + r) >> 1;
if (x <= mid) {
insert(t[p].lc, t[q].lc, l, mid, x, y);
} else {
insert(t[p].rc, t[q].rc, mid + 1, r, x, y);
}
}
int ask(int p, int l, int r, int x) {
if (l == r) return t[p].val;
int mid = (l + r) >> 1;
if (x <= mid) {
return ask(t[p].lc, l, mid, x);
} else {
return ask(t[p].rc, mid + 1, r, x);
}
}
}
// AC 自动机(大字符集)
namespace AC {
const int SIZE = 1000100; // 多模式串长度总和,需要根据实际问题调整
int nodeCount;
struct node {
std::map<int, int> trans;
int fail;
} t[SIZE];
int root[SIZE];
int newnode() {
int p = ++ nodeCount;
t[p].trans.clear();
t[p].fail = 0;
return p;
}
void init() {
nodeCount = 0, newnode(); // 根节点为 1
}
void insert(const std::vector<int> &a) {
int p = 1;
for (int v : a) {
if (!t[p].trans.contains(v)) t[p].trans[v] = newnode();
p = t[p].trans[v];
}
}
void build_fail() {
SGT::init(), root[0] = 0;
t[1].fail = 0;
std::queue<int> q;
q.push(1);
while (q.size()) {
int u = q.front(); q.pop();
root[u] = root[t[u].fail];
for (auto [c, v] : t[u].trans) {
SGT::insert(root[u], root[u], 1, V, c, v);
t[v].fail = SGT::ask(root[t[u].fail], 1, V, c);
q.push(v);
}
}
}
}AC 自动机查询所有模式串在文本串中的出现位置:
将所有询问串 t 去重之后,所有询问串 t 在文本串 s 中的出现次数之和不超过 \mathcal{O}(|s|\sqrt{\sum |t|}) 级别。
因为询问串的串长 |t| 种类数不超过 \mathcal{O}(\sqrt{\sum |t|}) 级别,同一长度的询问串 endpos 各不相同。
对询问串建 AC 自动机(trie 图),每个节点记录一下向上跳 fail 指针遇到的最近询问节点 up。
然后从左到右扫描 s,扫描到右端点 r 时,维护以 r 结尾的最长匹配串对应的状态。然后在当前状态不断地跳 up 指针,去更新(记录)当前询问串在 s 中的 endpos。
SA
序列 SA 的求法:
- \mathcal{O}(n \log^2 n):sort + 倍增 + hash。当比较函数时间开销较大时,尝试使用
std::stable_sort()。 - \mathcal{O}(n \log n):倍增 + 基数排序(双关键字排序)。
- \mathcal{O}(n):DC3,SA-IS。
height 数组:\mathrm{height}_i = \mathrm{LCP}(\mathrm{sa}_{i - 1}, \mathrm{sa}_i)
height 数组求后缀 LCP:后缀 \mathrm{sa}_i, \mathrm{sa}_j (i < j) 的最长公共前缀为
本质不同子串个数:
(序列 SA)height 数组的性质:\mathrm{height}_{\mathrm{rk}_i} \geq \mathrm{height}_{\mathrm{rk}_{i - 1}} - 1
证明:
- 当 \mathrm{height}_{\mathrm{rk}_{i - 1}} = 0 时,命题成立。
- 当 \mathrm{height}_{\mathrm{rk}_{i - 1}} \geq 1 时,考虑到后缀排序将“前缀相近的后缀”放到一起,所以 \mathrm{height}_i 可以视为字典序小于 \mathrm{sa}_i 的后缀与 \mathrm{sa}_i 的 LCP 最大值。记 u = \mathrm{sa}_{\mathrm{rk}_{i - 1} - 1},则有 s_u = s_{i - 1},于是 s[u + 1 : n] 的字典序比 s[i : n] 更小,则必然存在一个字典序小于 s[i : n] 的后缀使得与其的 LCP 大于等于 \mathrm{height}_{\mathrm{rk}_{i - 1}} - 1,故命题成立。
0x22 SA.cpp:
// 后缀数组
struct SuffixArray {
int n, t;
std::vector<int> sa, rk, height;
std::vector<std::vector<int>> f;
SuffixArray() {}
SuffixArray(const auto &s) {
build(s);
}
void build(const auto &s) {
n = s.size() - 1; // s 下标从 1 开始
int m = 256;
sa.resize(n + 1), rk.resize(n + 1), height.resize(n + 1);
std::vector<int> cnt(std::max(n, m) + 1), id(n + 1), px(n + 1), tmp(2 * n + 1);
auto same = [&] (int x, int y, int k) {
return tmp[x] == tmp[y] && tmp[x + k] == tmp[y + k];
};
for (int i = 1; i <= n; i ++) cnt[rk[i] = s[i]] ++;
for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) sa[cnt[rk[i]] --] = i;
for (int k = 1, p = 0; k < n; k <<= 1, m = p) {
p = 0;
for (int i = n - k + 1; i <= n; i ++) id[++ p] = i;
for (int i = 1; i <= n; i ++)
if (sa[i] > k) id[++ p] = sa[i] - k;
for (int i = 1; i <= m; i ++) cnt[i] = 0;
for (int i = 1; i <= n; i ++) cnt[px[i] = rk[id[i]]] ++;
for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) sa[cnt[px[i]] --] = id[i];
p = 0;
for (int i = 1; i <= n; i ++) tmp[i] = rk[i];
for (int i = 1; i <= n; i ++) rk[sa[i]] = same(sa[i - 1], sa[i], k) ? p : ++ p;
if (p == n) break;
}
if (n == 1) rk[1] = 1;
for (int i = 1, h = 0; i <= n; i ++) {
int j = sa[rk[i] - 1];
if (h) h --;
while (i + h <= n && j + h <= n && s[i + h] == s[j + h]) h ++;
height[rk[i]] = h;
}
t = std::__lg(n);
f.assign(t + 1, std::vector<int>(n + 1));
for (int i = 1; i <= n; i ++) {
f[0][i] = height[i];
}
for (int j = 1; j <= t; j ++) {
for (int i = 1; i <= n - (1 << j) + 1; i ++) {
f[j][i] = std::min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
}
}
int ask(int l, int r) {
int k = std::__lg(r - l + 1);
return std::min(f[k][l], f[k][r - (1 << k) + 1]);
}
int lcp(int i, int j) {
if (i == j) return n - i + 1;
auto [l, r] = std::minmax(rk[i], rk[j]);
return ask(l + 1, r);
}
};SAM
SAM 与其他后缀数据结构的关系:
- 后缀 trie:一个字符串的所有后缀构成的 trie。
- 后缀 trie 上建 AC 自动机的 fail 指针:表示删除当前状态所表示的串的首字母。
- 后缀树:后缀 trie 虚树化(仅保留所有后缀在后缀 trie 上的终止节点,以及两两 LCA)。
- 后缀自动机的 parent 树:反串的后缀树。
SAM:SAM 是一个状态自动机,形态是 DAG。
- 一个起点,若干终点。
- 原串的所有本质不同的子串,与在 SAM 上从起点开始到任意点结束的所有路径一一对应,不重不漏。
- SAM 主要考虑两种边:
- 普通转移边:表示在当前状态所表示的串后面加一个字符。
- 后缀链接 link:表示将当前状态所表示的最短串的首字母删除。这类边构成一棵树,称作 parent 树。
- SAM 点数 \leq 2n - 1,边数 \leq 3n - 4。
endpos 集合:子串 s 的所有终止位置的集合,记作 \mathrm{endpos}(s)。
- SAM 中的每一个状态,都对应一个 endpos 等价类。
- SAM 中的每一个状态(endpos 等价类),包含的子串长度构成一个连续段,且短串是长串的后缀。
- 对于字符串 s_1, s_2 (|s_1| \leq |s_2|):
- 若 s_1 为 s_2 的后缀,则 \mathrm{endpos}(s_1) \supseteq \mathrm{endpos}(s_2)。
- 否则 \mathrm{endpos}(s_1) \bigcap \mathrm{endpos}(s_2) = \varnothing。
endpos 集合的维护:在 parent 树上使用**(可持久化)线段树合并**维护。
在 parent 树上,节点 p 的 endpos 集合为 \mathrm{subtree}(p) 中所有节点 endpos 集合的并集。为此,我们在 s[1 : i] 对应状态的 endpos 集合里插入位置 i,然后使用数据结构合并子树的 endpos 集合。
当字符集很大时,需要用到 std::map 建立 SAM。
0x22 SAM.cpp:
// 后缀自动机
namespace SAM {
const int SIZE = N * 2;
int nodeCount, Last;
struct node {
int trans[26];
int link, maxl;
} t[SIZE];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].maxl = 0;
return p;
}
void init() {
nodeCount = 0, Last = 1, newnode(); // 根节点为 1
}
void extend(int c) {
int p = Last, np = Last = newnode();
t[np].maxl = t[p].maxl + 1;
for (; p && t[p].trans[c] == 0; p = t[p].link) {
t[p].trans[c] = np;
}
if (!p) {
t[np].link = 1;
} else {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
t[np].link = q;
} else {
int nq = newnode();
t[nq] = t[q], t[nq].maxl = t[p].maxl + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
}
}
}
}SAM 子串定位:求 s[l : r] 在 SAM 中的对应状态
先定位 s[1 : r] 在 SAM 中的对应状态(在构造 SAM 的过程中记录一下),然后在 parent 树上倍增,找到深度最浅的满足 \mathrm{maxl} \geq r - l + 1 的状态。
SAM 子串匹配:给定模式串 S 与文本串 T,对每个右端点 r 求最左端的 l 使得 T[l : r] 为 S 的子串
当 r 扩展时,不断地跳后缀链接(这里令 \mathrm{len} 变为对应状态的 \mathrm{maxl}),直到跳到根节点或存在相应的转移边为止。
若存在相应的转移边,则走该转移边(这里令 \mathrm{len} \gets \mathrm{len} + 1)。
int p = 1, len = 0; // 当前匹配到的状态与长度
for (int i = 1; i <= m; i ++) {
int c = T[i] - 'a';
while (p > 1 && !SAM::t[p].trans[c]) {
p = SAM::t[p].link, len = SAM::t[p].maxl;
}
if (SAM::t[p].trans[c]) {
p = SAM::t[p].trans[c], len ++;
}
// 此时的 p 与 len,就是以 i 为结尾时匹配到的最长状态与长度
}子 SAM:给定模式串 S 与文本串 T,让 T 在 S[l : r] 中进行匹配
判断由 S[l : r] 组成的子 SAM 是否存在相应的转移边,首先在原 SAM 就要存在相应的转移边,并且原 SAM 中新状态的 endpos 集合在区间 [l + \mathrm{len}' - 1, r] 中至少要有一个元素。
失配时,应先尝试 \mathrm{len} \gets \mathrm{len} - 1 然后继续匹配,而非直接跳失配链接。
SAM 前端删除:在一个状态的前面删除字符,求新状态
若当前长度等于当前状态的 \mathrm{minl},则跳后缀链接。
SAM 前端插入:在一个状态的前面添加字符,求新状态
维护每个状态 u 对应 endpos 集合的任意一个元素 \mathrm{pos}_u,就可以做到在原串中定位状态 u。
- 若长度等于当前状态的 \mathrm{maxl}:则相当于在 parent 树上向某一个儿子走。在构建 parent 树的时候,预处理出每个状态的极长串前面加一个字符 c 后会走到哪个儿子即可(枚举 u 以及其儿子 v,根据 \mathrm{pos}_v 在原串中定位,即可得知从 u 到 v 需要添加什么字符)。
- 若长度小于当前状态的 \mathrm{maxl}:相当于要考虑当前状态是否能够容纳新串,根据 \mathrm{pos}_u 在原串中定位,判断新加的字符是否与原串对应位置上的字符匹配。
0x22 SAM 前端操作.cpp:
// 后缀自动机(前端操作)
namespace SAM {
const int SIZE = N * 2;
int strL, str[N];
int nodeCount, Last;
struct node {
int trans[26];
int link, maxl, pos;
} t[SIZE];
int net[SIZE][26];
std::vector<int> son[SIZE];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = net[p][c] = 0;
t[p].link = t[p].maxl = t[p].pos = 0;
son[p].clear();
return p;
}
void init() {
nodeCount = 0, Last = 1, newnode(); // 根节点为 1
str[strL = 0] = -1;
}
void extend(int c) {
int p = Last, np = Last = newnode();
str[++ strL] = c, t[np].pos = strL;
t[np].maxl = t[p].maxl + 1;
for (; p && t[p].trans[c] == 0; p = t[p].link) {
t[p].trans[c] = np;
}
if (!p) {
t[np].link = 1;
} else {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
t[np].link = q;
} else {
int nq = newnode();
t[nq] = t[q], t[nq].maxl = t[p].maxl + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
}
}
}
void dfs_init(int u) {
for (int v : son[u]) {
net[u][str[t[v].pos - t[u].maxl]] = v;
dfs_init(v);
}
}
void build_tree() {
for (int i = 2; i <= nodeCount; i ++) {
son[t[i].link].push_back(i);
}
dfs_init(1);
}
void push_front(int &p, int &len, int c) {
if (len == t[p].maxl) {
p = net[p][c];
} else if (str[t[p].pos - len] != c) {
p = 0;
}
len = p ? len + 1 : 0;
}
}SAM 补节点:在 parent 树中,补充询问对应的状态
parent 树是反串的后缀树,而后缀树又是后缀 trie 虚树化(仅保留所有后缀在后缀 trie 上的终止节点,以及两两 LCA)。
由于询问串 s[l : r] 在 SAM 上的状态可能不完全覆盖 \mathrm{minl} \sim \mathrm{maxl}(为该区间的一个前缀),于是我们离线将所有询问串在 SAM 上的状态找出来,然后将状态划分,建立有关询问串的虚拟节点(补充有关询问串的虚树结构)。此时所有询问串一定完整地覆盖了从当前状态到根的路径,且总节点数不超过 2n + m。
简化了 parent 树的结构,降低了讨论难度。
广义 SAM:对多模式串建立 SAM
0x22 广义 SAM(离线).cpp:
// 广义 SAM(离线)
namespace GSAM {
const int SIZE = N * 2;
int trieCount, trie[N][26], site[N];
int nodeCount;
struct node {
int trans[26];
int link, maxl;
} t[SIZE];
int newtrie() {
int p = ++ trieCount;
for (int c = 0; c < 26; c ++) trie[p][c] = 0;
site[p] = 0;
return p;
}
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].maxl = 0;
return p;
}
void init() {
trieCount = 0, newtrie(); // trie 根节点为 1
nodeCount = 0, newnode(); // GSAM 根节点为 1
}
void insert(const std::string &s) {
int p = 1;
for (char ch : s) {
int v = ch - 'a';
if (!trie[p][v]) trie[p][v] = newtrie();
p = trie[p][v];
}
}
int extend(int Last, int c) {
int p = Last, np = newnode();
t[np].maxl = t[p].maxl + 1;
for (; p && t[p].trans[c] == 0; p = t[p].link) {
t[p].trans[c] = np;
}
if (!p) {
t[np].link = 1;
} else {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
t[np].link = q;
} else {
int nq = newnode();
t[nq] = t[q], t[nq].maxl = t[p].maxl + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
}
}
return np;
}
void build() {
std::queue<int> q;
q.push(1), site[1] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i ++) {
if (trie[u][i]) {
site[trie[u][i]] = extend(site[u], i);
q.push(trie[u][i]);
}
}
}
}
}0x22 广义 SAM(在线).cpp:
// 广义 SAM(在线)
// 在插入一个串之前,需要令 GSAM::Last = 1
namespace GSAM {
const int SIZE = N * 2;
int nodeCount, Last;
struct node {
int trans[26];
int link, maxl;
} t[SIZE];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].maxl = 0;
return p;
}
void init() {
nodeCount = 0, Last = 1, newnode(); // 根节点为 1
}
void extend(int c) {
int p = Last;
if (t[p].trans[c]) {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
Last = q;
} else {
int nq = newnode();
t[nq] = t[q], t[nq].maxl = t[p].maxl + 1;
t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
Last = nq;
}
} else {
int np = Last = newnode();
t[np].maxl = t[p].maxl + 1;
for (; p && t[p].trans[c] == 0; p = t[p].link) {
t[p].trans[c] = np;
}
if (!p) {
t[np].link = 1;
} else {
int q = t[p].trans[c];
if (t[q].maxl == t[p].maxl + 1) {
t[np].link = q;
} else {
int nq = newnode();
t[nq] = t[q], t[nq].maxl = t[p].maxl + 1;
t[np].link = t[q].link = nq;
for (; p && t[p].trans[c] == q; p = t[p].link) {
t[p].trans[c] = nq;
}
}
}
}
}
}PAM
PAM:PAM 是一个状态自动机,形态为由两棵树构成的森林。
- 两个起点(偶根为 0,奇根为 1),若干终点。
- 原串的所有本质不同的回文子串,与 PAM 上的所有状态一一对应,不重不漏。
- PAM 主要考虑两种边:
- 普通转移边:表示在当前状态所表示的串前后各加一个字符。
- 后缀链接 link:表示当前状态所表示的串的最长回文后缀。这类边构成一棵树,称作 parent 树。
- 偶根的 link 指向奇根,而我们不关心奇根的 link(因为奇根不可能失配,奇根转移出的下一个状态是单个字符,必定为回文串)。
- PAM 点数(本质不同回文子串个数)\leq n。因为在任意串后面加一个字符,由反证法可知本质不同回文子串至多 +1。
0x22 PAM.cpp:
// 回文自动机
namespace PAM {
int strL, str[N];
int nodeCount, Last;
struct node {
int trans[26];
int link, len;
} t[N];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].len = 0;
return p;
}
void init() {
nodeCount = -1, Last = 1, newnode(), newnode(); // 偶根为 0,奇根为 1
str[strL = 0] = -1;
t[0].len = 0, t[0].link = 1;
t[1].len = -1;
}
int find(int p) {
while (str[strL - t[p].len - 1] != str[strL]) {
p = t[p].link;
}
return p;
}
void extend(int c) {
str[++ strL] = c;
int p = find(Last);
if (!t[p].trans[c]) {
int np = newnode();
t[np].len = t[p].len + 2;
t[np].link = t[find(t[p].link)].trans[c];
t[p].trans[c] = np;
}
Last = t[p].trans[c];
}
}PAM half 指针:表示当前状态所表示的串,长度小于等于该串一半的最长回文后缀。
0x22 PAM half.cpp:
// 回文自动机 half
namespace PAM {
int strL, str[N];
int nodeCount, Last;
struct node {
int trans[26];
int link, half, len;
} t[N];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].half = t[p].len = 0;
return p;
}
void init() {
nodeCount = -1, Last = 1, newnode(), newnode(); // 偶根为 0,奇根为 1
str[strL = 0] = -1;
t[0].len = 0, t[0].link = 1;
t[1].len = -1;
}
int find(int p) {
while (str[strL - t[p].len - 1] != str[strL]) {
p = t[p].link;
}
return p;
}
int find_half(int p, int L) {
while (t[p].len + 2 > L || str[strL - t[p].len - 1] != str[strL]) {
p = t[p].link;
}
return p;
}
void extend(int c) {
str[++ strL] = c;
int p = find(Last);
if (!t[p].trans[c]) {
int np = newnode();
t[np].len = t[p].len + 2;
t[np].link = t[find(t[p].link)].trans[c];
t[np].half = t[np].len > 2 ? t[find_half(t[p].half, t[np].len / 2)].trans[c] : t[np].link;
t[p].trans[c] = np;
}
Last = t[p].trans[c];
}
}Palindrome Series
当 t 是回文串 s 的后缀时,t 是 s 的 border \iff t 是回文串。
所以回文串 s 的回文后缀一定是 border,反之亦然。
Palindrome Series:回文串 s 的所有回文后缀,可以被划分成至多 \left\lceil \log_2 n \right\rceil 个等差数列。
进一步,每个等差数列都具有一定的周期性。同一个等差数列里的字符串,都可以被表示成
或
其中 W, A, B 均为字符串。
PAM series-link:对于 PAM 上的每个状态 u
- \mathrm{diff}_u = \mathrm{len}_u - \mathrm{len}_{\mathrm{link}_u}。
- \mathrm{slink}_u 表示 u 不断跳后缀链接 link,跳到的第一个满足 \mathrm{diff}_v \neq \mathrm{diff}_u 的节点 v。
我们称 diff 值相同的连续 link 链为一个 Series,Series 中的回文串长度都构成一个等差数列。那么 \mathrm{slink}_u 就表示 u 所在的 Series 对应的下一个 Series 的最长回文节点。
上述理论可以用来优化一类 dp 问题:
(其中 \oplus 表示一种运算,例如 + 或者 \min)
考虑将一个 Series 表示的所有回文串的 dp 值都记录到最长的回文串上,设 g_u 表示 u 所在 Series 的 dp 贡献之和(其中 u 作为该 Series 中最长回文节点)。
若节点 u 最近一次在位置 i 结尾,且 \mathrm{diff}_u = \mathrm{diff}_{\mathrm{link}_u},则 \mathrm{link}_u 在 i 之前(严格早于 i)的最近一次出现,结尾于位置 i - \mathrm{diff}_u。
假设当前处理到位置 i,沿着 slink 处理每一个 Series 的贡献。设当前节点为 u,则 u 所在 Series 中最短回文串长度为 \mathrm{diff}_u + \mathrm{len}_{\mathrm{slink}_u},除了最短回文串的其他贡献,恰好等于在位置 i - \mathrm{diff}_u 时已经维护好的 g_{\mathrm{link}_u}。因此有转移:
0x22 PAM series-link.cpp:
// 回文自动机 series-link
namespace PAM {
int strL, str[N];
int nodeCount, Last;
struct node {
int trans[26];
int link, len;
int diff, slink;
} t[N];
int g[N];
int newnode() {
int p = ++ nodeCount;
for (int c = 0; c < 26; c ++) t[p].trans[c] = 0;
t[p].link = t[p].len = 0;
t[p].diff = t[p].slink = 0;
g[p] = 0x3f3f3f3f;
return p;
}
void init() {
nodeCount = -1, Last = 1, newnode(), newnode(); // 偶根为 0,奇根为 1
str[strL = 0] = -1;
t[0].len = 0, t[0].link = 1;
t[1].len = -1;
}
int find(int p) {
while (str[strL - t[p].len - 1] != str[strL]) {
p = t[p].link;
}
return p;
}
void extend(int c) {
str[++ strL] = c;
int p = find(Last);
if (!t[p].trans[c]) {
int np = newnode();
t[np].len = t[p].len + 2;
t[np].link = t[find(t[p].link)].trans[c];
t[np].diff = t[np].len - t[t[np].link].len;
t[np].slink = t[np].diff == t[t[np].link].diff ? t[t[np].link].slink : t[np].link;
t[p].trans[c] = np;
}
Last = t[p].trans[c];
}
int ask(int x, int i) {
int ans = 0x3f3f3f3f;
for (int u = x; u > 1; u = t[u].slink) {
g[u] = f[i - t[u].diff - t[t[u].slink].len];
if (t[u].diff == t[t[u].link].diff) {
chmin(g[u], g[t[u].link]);
}
chmin(ans, g[u]);
}
return ans;
}
}