「v4」0x20 字符串

    「v4」0x20 字符串

    同步于 2026-11-11,花费 14,451,581 tok。

    0x21 字符串 I

    哈希

    字符串哈希

    字符串哈希:字符串哈希要求数据有序。将字符串的元素通过某种不具有交换律的运算结合(例如字符串拼接,矩阵乘法 …)。

    通常将字符串 ss 视为一个 base\mathrm{base} 进制数,即

    f(s)≡∑i=1lsi×basel−i(modM)f(s) \equiv \sum_{i = 1}^{l} s_i \times \mathrm{base}^{l - i} \pmod M

    其中模数 MM 尽量为大质数,并且尽量对两个大质数模数 M1,M2M_1, M_2 各求一次哈希(双哈希)

    静态字符串区间哈希:

    prei=prei−1×base+sif(s[l:r])=prer−prel−1×baser−l+1\begin{gathered} \mathrm{pre}_i = \mathrm{pre}_{i - 1} \times \mathrm{base} + s_i \\ f(s[l : r]) = \mathrm{pre}_r - \mathrm{pre}_{l - 1} \times \mathrm{base}^{r - l + 1} \end{gathered}

    动态字符串区间哈希:区间哈希值可以合并。设左右两个区间的长度与哈希值分别为 (l1,h1),(l2,h2)(l_1, h_1), (l_2, h_2),将它们拼接形成大区间的长度与哈希值为

    (l1+l2,h1×basel2+h2)(l_1 + l_2, h_1 \times \mathrm{base}^{l_2} + h_2)

    可以使用线段树动态维护。

    卡自然溢出哈希(Hash Killer I):

    base\mathrm{base} 为偶数:此时 base64≡0(mod264)\mathrm{base}^{64} \equiv 0 \pmod{2^{64}}。所以两个长度 >64> 64 且后 6464 位相同但不完全相同的字符串就会哈希冲突。

    base\mathrm{base} 为奇数:使用 Thue Morse 序列攻击。对于二进制串 ss,设 s‾\overline{s} 表示 ss 按位取反后得到的串。

    Thue Morse 序列:t0=0t_0 = \mathtt{0},ti=ti−1+ti−1‾t_i = t_{i - 1} + \overline{t_{i - 1}}。此时

    f(ti)=base2i−1f(ti−1)+f(ti−1‾)f(ti‾)=base2i−1f(ti−1‾)+f(ti−1)\begin{gathered} f(t_i) = \mathrm{base}^{2^{i - 1}} f(t_{i - 1}) + f(\overline{t_{i - 1}}) \\ f(\overline{t_i}) = \mathrm{base}^{2^{i - 1}} f(\overline{t_{i - 1}}) + f(t_{i - 1}) \end{gathered}

    记 hi=f(ti)−f(ti‾)h_i = f(t_i) - f(\overline{t_i}),有 hi=(base2i−1−1)hi−1h_i = \left(\mathrm{base}^{2^{i - 1}} - 1\right)h_{i - 1}。由于

    base2i−1−1=(base2i−2+1)(base2i−3+1)…(base+1)(base−1)\mathrm{base}^{2^{i - 1}} - 1 = (\mathrm{base}^{2^{i - 2}} + 1)(\mathrm{base}^{2^{i - 3}} + 1)\dots(\mathrm{base} + 1)(\mathrm{base} - 1)

    其中每一项都是偶数,所以 2i∣base2i−1−12^i \mid \mathrm{base}^{2^{i - 1}} - 1。于是 2i(i+1)2∣hi2^{\frac{i(i + 1)}{2}} \mid h_i,因此 t11t_{11} 与 t11‾\overline{t_{11}} 就会哈希冲突。

    Thue Morse 序列的规律:第 xx (x≥0x \geq 0) 位上的值等于 popcount(x) mod 2\mathrm{popcount}(x) \bmod 2。

    卡大质数哈希(Hash Killer II):使用生日悖论攻击。

    集合哈希

    集合哈希:集合哈希要求数据无序。将集合的元素通过某种映射规则转化后,再通过某种具有交换律的运算结合。

    可用的映射规则:用来打乱原来可能有的某些性质。

    • 查表映射:给原数值 xx 随机赋一个新数值 cxc_x 并存入表中。

    可用的结合方式:

    • 使用加法结合:

      f(S)=∑x∈Sshift(x)f(S) = \sum_{x \in S} \mathrm{shift}(x)
    • 使用异或结合(异或哈希):

      f(S)=⨁x∈Sshift(x)f(S) = \bigoplus_{x \in S} \mathrm{shift}(x)

    此时出现偶数次元素无贡献,出现奇数次元素只贡献一次。

    异或哈希判完全平方数:定义完全异或性函数 ff,对于任意正整数 x,yx, y 都有 f(xy)=f(x)⊕f(y)f(xy) = f(x) \oplus f(y)。先对 1∼n1 \sim n 进行一次线性筛。给其中的所有质数 pp 对应的 f(p)f(p) 赋一个范围较大的随机数,其余合数的 ff 值通过线性筛得出。

    此时 xx 为完全平方数,极大概率等价于 f(x)=0f(x) = 0。

    当待判断的数可以表示为若干个 [1,n][1, n] 范围内整数的乘积时,就可以根据这些数的 ff 函数异或和求出该数的 ff 函数,从而快速判断其是否为完全平方数。

    kmp

    字符串的 border:对字符串 ss 与整数 0≤r<∣s∣0 \leq r < |s|,若 ss 长度为 rr 的前缀与后缀相等,则称 ss 长度为 rr 的前缀为 ss 的 border。

    字符串的周期:对字符串 ss 与整数 1≤p≤∣s∣1 \leq p \leq |s|,若对于任意 i∈[1,∣s∣−p]i \in [1, |s| - p] 均有 si=si+ps_i = s_{i + p},则称 pp 为 ss 的周期。特别地,若 pp 整除 ∣s∣|s|,则称 pp 为 ss 的整周期。

    相当于 s[1:n−p]=s[p+1:n]s[1 : n - p] = s[p + 1 : n],所以 ss 有长度为 rr 的 border   ⟺  \iff ∣s∣−r|s| - r 是 ss 的周期。

    kmp:记 nexti\mathrm{next}_i 表示字符串 s[1:i]s[1 : i] 的最长 border 的长度。

    利用 border 的 border 还是原串 border 的性质,可以 O(n)\mathcal{O}(n) 求解前缀函数。

    进一步,s[1:i]s[1 : i] 的所有 border 为 nexti,nextnexti,…\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,qp, q 是 ss 的周期且 p+q≤np + q \leq n,则 gcd⁡(p,q)\gcd(p, q) 也是 ss 的周期。

    证明:不妨设 p>qp > q,下面证明 p−qp - q 也是 ss 的周期。

    • 当 i≤qi \leq q 时,si=si+p=si+p−qs_i = s_{i + p} = s_{i + p - q}。
    • 当 i>qi > q 时,si=si−q=si+p−qs_i = s_{i - q} = s_{i + p - q}。

    所以 p−qp - q 也是 ss 的周期,运用辗转相除法可知 gcd⁡(p,q)\gcd(p, q) 也是 ss 的周期。

    周期引理:若 p,qp, q 是 ss 的周期且 p+q−gcd⁡(p,q)≤np + q - \gcd(p, q) \leq n,则 gcd⁡(p,q)\gcd(p, q) 也是 ss 的周期。

    长 border 结构:ss 的所有长度 ≥⌊n2⌋\geq \left\lfloor\frac{n}{2}\right\rfloor 的 border,它们与 nn 共同构成一个等差数列,公差为 ss 的最小周期。

    证明:设 n−p,n−qn - p, n - q (p,q≤⌈n2⌉p, q \leq \left\lceil \frac{n}{2} \right\rceil) 是两个不同的 border,其中 n−pn - p 是最大的 border。

    已知 p,qp, q 是 ss 的周期,由于 p+q≤np + q \leq n,可知 gcd⁡(p,q)\gcd(p, q) 也是 ss 的周期。由于 n−pn - p 是最大 border,所以 pp 是最小周期。结合两个条件可得 gcd⁡(p,q)=p\gcd(p, q) = p,即 p∣qp \mid q。同时,周期的整数倍也一定是周期。

    综上,ss 的所有长度 ≥⌊n2⌋\geq \left\lfloor\frac{n}{2}\right\rfloor 的 border 与 nn 共同构成一个公差为 pp(最小周期)的等差数列。

    短周期结构:ss 的所有长度 ≤⌈n2⌉\leq \left\lceil \frac{n}{2} \right\rceil 的周期,都是 ss 最小周期的倍数。

    证明同「长 border 结构」。

    字符串 border 结构:ss 的所有 border 可以被划分成至多 ⌈log⁡2n⌉\left\lceil \log_2 n \right\rceil 个等差数列。

    进一步,每个等差数列都具有一定的周期性。同一个等差数列里的字符串,都可以被表示成

    W,W+A,W+A2,…,W+AkW, W + A, W + A^2, \dots, W + A^k

    或

    W,B+W,B2+W,…,Bk+WW, B + W, B^2 + W, \dots, B^k + W

    其中 W,A,BW, A, B 均为字符串。

    证明:设 [2i,2i+1)[2^i, 2^{i + 1}) 中最大的 border 为 pp,那么段内的其余 border 都是 s[1:p]s[1 : p] 的 border,且长度 ≥⌊p2⌋\geq \left\lfloor \frac{p}{2} \right\rfloor,由「长 border 结构」可知段内构成一个等差数列。

    推论:ss 的所有公差 ≥d\geq d 的 border 的等差数列总大小是 O(nd)\mathcal{O}\left( \frac{n}{d} \right) 的。

    Misc:

    • 若 ss 在 tt 中的某两个匹配 s1,s2s_1, s_2 有重合,且起始位置相差 dd,则 dd 均为 ss 与 s1∪s2s_1 \cup s_2(两个匹配区间并)的周期。
    • 若 ∣s∣≥∣t∣2|s| \geq \frac{|t|}{2},则 ss 在 tt 中的匹配起始位置形成等差数列。若该等差数列至少有 33 项,则公差为 ss 的最小周期 per(s)\mathrm{per}(s)。

    Z Algorithm

    Z Algorithm:记 ZiZ_i 表示字符串 ss 与 s[i:n]s[i : n] 的最长公共前缀(LCP)长度。在某些情况下,可能会记 Z1=0Z_1 = 0。

    考虑从前向后扫。维护一个右端点最靠右,且与 ss 的前缀匹配的子串 s[l:r]s[l : r]。

    • 若 i≤ri \leq r,则

      Zi≥min⁡(Zi−l+1,r−i+1)Z_i \geq \min(Z_{i - l + 1}, r - i + 1)
    • 若 i>ri > r,则

      Zi≥0Z_i \geq 0

    在当前 ZiZ_i 的基础上不断尝试扩展。

    注意到单次枚举的次数为 max⁡{l+Zl−1}\max\{l + Z_l - 1\} 的增量,时间复杂度 O(n)\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:记 pip_i 表示以位置 ii 为中心的最长回文子串的半径(含中心)。

    考虑从前向后扫。维护一个右端点最靠右的回文子串,不妨记该回文串的中心为 kk。

    • 若 i≤k+pk−1i \leq k + p_k - 1,则

      pi≥min⁡(k+pk−i,p2k−i)p_i \geq \min(k + p_k - i, p_{2k - i})
    • 若 i>k+pk−1i > k + p_k - 1,则

      pi≥0p_i \geq 0

    在当前 pip_i 的基础上不断尝试扩展。

    注意到单次枚举的次数为 max⁡{k+pk−1}\max\{k + p_k - 1\} 的增量,时间复杂度 O(n)\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;
    }

    反回文串:对于长度为 nn 的字符串 ss,若对于任意 i∈[1,n]i \in [1, n] 均有 si≠sn−i+1s_i \neq s_{n - i + 1},则称 ss 为反回文串。

    01 串的反 manacher:相当于对于每两个相邻字符的中间,求以该位置为中心的最长反回文子串的半径。注意我们只需要考虑长度为偶数的串。

    当字符集大小为 22 时,考虑形如 ABCD 的字符串,若已知 A≠B,A≠D,B≠CA \neq B, A \neq D, B \neq C,可以推出 C≠DC\neq D,所以 manacher 的对称复用逻辑还是正确的。但是字符集大小超过 22 的时候,上述推理就不成立了。

    具体实现时,只需要将 manacher 偶回文串指针扩展过程中的 == 改成 != 即可。

    Lyndon 分解

    Lyndon 串:对于字符串 ss,若 ss 的字典序小于 ss 的所有非空真后缀,则称 ss 为 Lyndon 串。

    等价定义:

    • 字符串 ss 的字典序严格小于 ss 的其他循环移位。
    • 对字符串 ss 的任意非空分解 s=uvs = uv,都有 u<vu < v。
    • 对字符串 ss 的任意非空分解 s=uvs = uv,都有 uv<vuuv < vu。

    Lyndon 串的拼接性质:

    • 若字符串 u,vu, v 均为 Lyndon 串并且 u<vu < v,则 uvuv 为 Lyndon 串,且 u<uv<vu < uv < v。
    • 若字符串 u,vu, v 均为 Lyndon 串并且 u<vu < v,则对于任意正整数 a,ba, b,均有 uavbu^av^b 为 Lyndon 串,且 u<uavb<vu < u^av^b < v。
    • 字符串 ss (∣s∣≥2|s| \geq 2) 是 Lyndon 串,当且仅当 s=uvs = uv (∣u∣>0,∣v∣>0,u<v|u| > 0, |v| > 0, \boldsymbol{u < v}) 并且 u,vu, v 均为 Lyndon 串。

    Lyndon 串的简单性质:

    • Lyndon 串不存在非空 border。
    • 截取 Lyndon 串的某个前缀,将其末字符增大,结果仍是 Lyndon 串(截出的前缀本身不必是 Lyndon 串)。
    • 若字符串 s1,s2s_1, s_2 满足 s1s_1 是 Lyndon 串且 s1>s2s_1 > s_2,则 s1>s22s_1 > s_2^2。

    Lyndon 分解:将字符串 ss 分解为 w1w2…wkw_1w_2\dots w_k,其中所有的 wiw_i 均为 Lyndon 串,且满足 w1≥w2≥⋯≥wkw_1 \geq w_2 \geq \dots \geq w_k。

    Lyndon 分解的性质:

    • Lyndon 分解存在且唯一。
    • 字符串 ss 是 Lyndon 串当且仅当 k=1k = 1。
    • 第一块 w1w_1:是原串最长的 Lyndon 前缀。
    • 最后一块 wkw_k:是原串最长的 Lyndon 后缀,也是原串字典序最小的非空后缀。

    Lyndon 分解(duval):维护三个指针 i,j,ki, j, k,将字符串分成三个部分:

    • s[1:i−1]s[1 : i - 1]:这部分的 Lyndon 分解已完成。
    • s[i:j−1]s[i : j - 1]:这部分可以被表示为 wc+vw^c + v,其中 ww 是一个 Lyndon 串,vv 是 ww 的可空真前缀。
    • s[j:n]s[j : n]:这部分还未处理,当前考虑的是位置 jj。

    其中 k=j−∣w∣k = j - |w|,那么 sks_k 表示继续循环下去时,位置 jj 应当出现的字符。

    接下来有三种情况:

    • sk=sjs_k = s_j:可以将 ww 继续循环下去,令 k←k+1k \gets k + 1,j←j+1j \gets j + 1。
    • sk<sjs_k < s_j:此时 wc+v+sjw^c + v + s_j 本身是一个 Lyndon 串,将其作为新的 ww,令 k←ik \gets i,j←j+1j \gets j + 1。
    • sk>sjs_k > s_j:将当前的 cc 个 ww 依次加入 Lyndon 分解,然后从 vv 的开头重新扫描。

    每一轮 jj 扫描的长度,不超过 ii 前进长度的两倍。时间复杂度 O(n)\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 串 ss (∣s∣≥2|s| \geq 2),记 ss 的最长 Lyndon 真后缀为 vv,此时 s=uvs = uv,记 (u,v)(u, v) 为 ss 的标准分解。

    最小表示法

    循环同构:若长度为 nn 的字符串 ss,可以选择一个起始位置 ii (1≤i≤n1 \leq i \leq n),使得 s[i:n]+s[1:i−1]=ts[i : n] + s[1 : i - 1] = t,则称 s,ts, t 循环同构。

    最小表示法:字符串 ss 的最小表示法,为与 ss 循环同构的所有字符串中,字典序最小的字符串。

    对于两个不同的起始位置 i,ji, j,已知它们的前 kk 位相同。考虑继续比较下一位:

    • 若 s(i+k) mod n>s(j+k) mod ns_{(i + k) \bmod n} > s_{(j + k) \bmod n},可以发现区间 [i,i+k][i, i + k] 内的起始位置都不能成为答案,因为对于起始位置 i+pi + p (p∈[0,k]p \in [0, k]) 来说,起始位置 j+pj + p 一定更优。所以此时可以跳过区间 [i,i+k][i, i + k] 的起始位置,令 i←i+k+1i \gets i + k + 1,k←0k \gets 0。
    • 若 s(i+k) mod n<s(j+k) mod ns_{(i + k) \bmod n} < s_{(j + k) \bmod n} 也是同理,跳过区间 [j,j+k][j, j + k] 的起始位置,令 j←j+k+1j \gets j + k + 1,k←0k \gets 0。
    • 若 s(i+k) mod n=s(j+k) mod ns_{(i + k) \bmod n} = s_{(j + k) \bmod n},令 k←k+1k \gets k + 1,然后继续比较。

    在跳转的过程中,若两个起始位置 i,ji, j 相同,则任选一个加一。最终 min⁡(i,j)\min(i, j) 即为最优的起始位置。

    时间复杂度 O(n)\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 查询与 xx 异或的最大值:从高位到低位贪心,有异走异,无异走同。

    01 trie 查询与 xx 异或的第 kk 大值:从高位到低位

    • 设当前考虑到第 ii 位,设 xx 的异位有 cnt\mathrm{cnt} 个数。
      • 若 k≤cntk \leq \mathrm{cnt},则查询 xx 的异位中,与 xx 异或的第 kk 大值。
      • 若 k>cntk > \mathrm{cnt},则查询 xx 的同位中,与 xx 异或的第 k−cntk - \mathrm{cnt} 大值。

    01 trie 查询与 xx 异或 ≥k\geq k 的信息:从高位到低位

    • 设当前考虑到第 ii 位:
      • 若 kk 的第 ii 位为 11,直接走 xx 的异位。
      • 若 kk 的第 ii 位为 00,统计 xx 的异位的贡献,然后走 xx 的同位。
    • 考虑完所有位之后,统计当前叶子节点的贡献。

    01 trie 全局异或 xx:从高位到低位,运用懒标记。

    设当前考虑到第 ii 位,若懒标记的第 ii 位为 11,则交换左右儿子。

    01 trie 维护集合异或和,支持插入、删除、全局 +1:从低位到高位

    • 额外维护:
      • cnt\mathrm{cnt}:当前状态的子树内插入数的个数。
      • xr\mathrm{xr}:当前状态的子树内的异或和。
    • 插入、删除:递归操作即可。
    • 全局 +1:交换当前节点的左右儿子,然后进入 00 转移边(未交换前是 11 转移边)的儿子进行递归交换。

    (因为二进制下 +1,相当于是从低位到高位找到第一个 00 将其改为 11,然后将前面的 11 都改为 00)

    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 中不存在的转移边 δ(p,c)\delta(p, c) 指向 δ(failp,c)\delta(\mathrm{fail}_p, c)。本质上是路径压缩。

    trie 图的普通转移边:从字符串 ss 指向 s′+cs' + c,其中 s′s' 为 ss 中满足 s′+cs' + 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 自动机查询所有模式串在文本串中的出现位置:

    将所有询问串 tt 去重之后,所有询问串 tt 在文本串 ss 中的出现次数之和不超过 O(∣s∣∑∣t∣)\mathcal{O}(|s|\sqrt{\sum |t|}) 级别。

    因为询问串的串长 ∣t∣|t| 种类数不超过 O(∑∣t∣)\mathcal{O}(\sqrt{\sum |t|}) 级别,同一长度的询问串 endpos 各不相同。

    对询问串建 AC 自动机(trie 图),每个节点记录一下向上跳 fail 指针遇到的最近询问节点 up。

    然后从左到右扫描 ss,扫描到右端点 rr 时,维护以 rr 结尾的最长匹配串对应的状态。然后在当前状态不断地跳 up 指针,去更新(记录)当前询问串在 ss 中的 endpos。

    SA

    序列 SA 的求法:

    • O(nlog⁡2n)\mathcal{O}(n \log^2 n):sort + 倍增 + hash。当比较函数时间开销较大时,尝试使用 std::stable_sort()。
    • O(nlog⁡n)\mathcal{O}(n \log n):倍增 + 基数排序(双关键字排序)。
    • O(n)\mathcal{O}(n):DC3,SA-IS。

    height 数组:heighti=LCP(sai−1,sai)\mathrm{height}_i = \mathrm{LCP}(\mathrm{sa}_{i - 1}, \mathrm{sa}_i)

    height 数组求后缀 LCP:后缀 sai,saj\mathrm{sa}_i, \mathrm{sa}_j (i<ji < j) 的最长公共前缀为

    LCP(sai,saj)=min⁡i<k≤j{heightk}\mathrm{LCP}(\mathrm{sa}_i, \mathrm{sa}_j) = \min_{i < k \leq j}\{\mathrm{height}_k\}

    本质不同子串个数:

    n(n+1)2−∑i=2nheighti\frac{n(n + 1)}{2} - \sum_{i = 2}^n \mathrm{height}_i

    (序列 SA)height 数组的性质:heightrki≥heightrki−1−1\mathrm{height}_{\mathrm{rk}_i} \geq \mathrm{height}_{\mathrm{rk}_{i - 1}} - 1

    证明:

    • 当 heightrki−1=0\mathrm{height}_{\mathrm{rk}_{i - 1}} = 0 时,命题成立。
    • 当 heightrki−1≥1\mathrm{height}_{\mathrm{rk}_{i - 1}} \geq 1 时,考虑到后缀排序将“前缀相近的后缀”放到一起,所以 heighti\mathrm{height}_i 可以视为字典序小于 sai\mathrm{sa}_i 的后缀与 sai\mathrm{sa}_i 的 LCP 最大值。记 u=sarki−1−1u = \mathrm{sa}_{\mathrm{rk}_{i - 1} - 1},则有 su=si−1s_u = s_{i - 1},于是 s[u+1:n]s[u + 1 : n] 的字典序比 s[i:n]s[i : n] 更小,则必然存在一个字典序小于 s[i:n]s[i : n] 的后缀使得与其的 LCP 大于等于 heightrki−1−1\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 点数 ≤2n−1\leq 2n - 1,边数 ≤3n−4\leq 3n - 4。

    endpos 集合:子串 ss 的所有终止位置的集合,记作 endpos(s)\mathrm{endpos}(s)。

    • SAM 中的每一个状态,都对应一个 endpos 等价类。
    • SAM 中的每一个状态(endpos 等价类),包含的子串长度构成一个连续段,且短串是长串的后缀。
    • 对于字符串 s1,s2s_1, s_2 (∣s1∣≤∣s2∣|s_1| \leq |s_2|):
      • 若 s1s_1 为 s2s_2 的后缀,则 endpos(s1)⊇endpos(s2)\mathrm{endpos}(s_1) \supseteq \mathrm{endpos}(s_2)。
      • 否则 endpos(s1)⋂endpos(s2)=∅\mathrm{endpos}(s_1) \bigcap \mathrm{endpos}(s_2) = \varnothing。

    endpos 集合的维护:在 parent 树上使用**(可持久化)线段树合并**维护。

    在 parent 树上,节点 pp 的 endpos 集合为 subtree(p)\mathrm{subtree}(p) 中所有节点 endpos 集合的并集。为此,我们在 s[1:i]s[1 : i] 对应状态的 endpos 集合里插入位置 ii,然后使用数据结构合并子树的 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]s[l : r] 在 SAM 中的对应状态

    先定位 s[1:r]s[1 : r] 在 SAM 中的对应状态(在构造 SAM 的过程中记录一下),然后在 parent 树上倍增,找到深度最浅的满足 maxl≥r−l+1\mathrm{maxl} \geq r - l + 1 的状态。

    SAM 子串匹配:给定模式串 SS 与文本串 TT,对每个右端点 rr 求最左端的 ll 使得 T[l:r]T[l : r] 为 SS 的子串

    当 rr 扩展时,不断地跳后缀链接(这里令 len\mathrm{len} 变为对应状态的 maxl\mathrm{maxl}),直到跳到根节点或存在相应的转移边为止。

    若存在相应的转移边,则走该转移边(这里令 len←len+1\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:给定模式串 SS 与文本串 TT,让 TT 在 S[l:r]S[l : r] 中进行匹配

    判断由 S[l:r]S[l : r] 组成的子 SAM 是否存在相应的转移边,首先在原 SAM 就要存在相应的转移边,并且原 SAM 中新状态的 endpos 集合在区间 [l+len′−1,r][l + \mathrm{len}' - 1, r] 中至少要有一个元素。

    失配时,应先尝试 len←len−1\mathrm{len} \gets \mathrm{len} - 1 然后继续匹配,而非直接跳失配链接。

    SAM 前端删除:在一个状态的前面删除字符,求新状态

    若当前长度等于当前状态的 minl\mathrm{minl},则跳后缀链接。

    SAM 前端插入:在一个状态的前面添加字符,求新状态

    维护每个状态 uu 对应 endpos 集合的任意一个元素 posu\mathrm{pos}_u,就可以做到在原串中定位状态 uu。

    • 若长度等于当前状态的 maxl\mathrm{maxl}:则相当于在 parent 树上向某一个儿子走。在构建 parent 树的时候,预处理出每个状态的极长串前面加一个字符 cc 后会走到哪个儿子即可(枚举 uu 以及其儿子 vv,根据 posv\mathrm{pos}_v 在原串中定位,即可得知从 uu 到 vv 需要添加什么字符)。
    • 若长度小于当前状态的 maxl\mathrm{maxl}:相当于要考虑当前状态是否能够容纳新串,根据 posu\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]s[l : r] 在 SAM 上的状态可能不完全覆盖 minl∼maxl\mathrm{minl} \sim \mathrm{maxl}(为该区间的一个前缀),于是我们离线将所有询问串在 SAM 上的状态找出来,然后将状态划分,建立有关询问串的虚拟节点(补充有关询问串的虚树结构)。此时所有询问串一定完整地覆盖了从当前状态到根的路径,且总节点数不超过 2n+m2n + 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 是一个状态自动机,形态为由两棵树构成的森林。

    • 两个起点(偶根为 00,奇根为 11),若干终点。
    • 原串的所有本质不同的回文子串,与 PAM 上的所有状态一一对应,不重不漏。
    • PAM 主要考虑两种边:
      • 普通转移边:表示在当前状态所表示的串前后各加一个字符。
      • 后缀链接 link:表示当前状态所表示的串的最长回文后缀。这类边构成一棵树,称作 parent 树。
    • 偶根的 link 指向奇根,而我们不关心奇根的 link(因为奇根不可能失配,奇根转移出的下一个状态是单个字符,必定为回文串)。
    • PAM 点数(本质不同回文子串个数)≤n\leq n。因为在任意串后面加一个字符,由反证法可知本质不同回文子串至多 +1+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

    当 tt 是回文串 ss 的后缀时,tt 是 ss 的 border   ⟺  \iff tt 是回文串。

    所以回文串 ss 的回文后缀一定是 border,反之亦然。

    Palindrome Series:回文串 ss 的所有回文后缀,可以被划分成至多 ⌈log⁡2n⌉\left\lceil \log_2 n \right\rceil 个等差数列。

    进一步,每个等差数列都具有一定的周期性。同一个等差数列里的字符串,都可以被表示成

    W,W+A,W+A2,…,W+AkW, W + A, W + A^2, \dots, W + A^k

    或

    W,B+W,B2+W,…,Bk+WW, B + W, B^2 + W, \dots, B^k + W

    其中 W,A,BW, A, B 均为字符串。

    PAM series-link:对于 PAM 上的每个状态 uu

    • diffu=lenu−lenlinku\mathrm{diff}_u = \mathrm{len}_u - \mathrm{len}_{\mathrm{link}_u}。
    • slinku\mathrm{slink}_u 表示 uu 不断跳后缀链接 link,跳到的第一个满足 diffv≠diffu\mathrm{diff}_v \neq \mathrm{diff}_u 的节点 vv。

    我们称 diff 值相同的连续 link 链为一个 Series,Series 中的回文串长度都构成一个等差数列。那么 slinku\mathrm{slink}_u 就表示 uu 所在的 Series 对应的下一个 Series 的最长回文节点。

    上述理论可以用来优化一类 dp 问题:

    fi=⨁s[j+1:i] is Palindromefjf_i = \bigoplus_{s[j + 1 : i] \ \text{is} \ \text{Palindrome}} f_j

    (其中 ⊕\oplus 表示一种运算,例如 ++ 或者 min⁡\min)

    考虑将一个 Series 表示的所有回文串的 dp 值都记录到最长的回文串上,设 gug_u 表示 uu 所在 Series 的 dp 贡献之和(其中 uu 作为该 Series 中最长回文节点)。

    若节点 uu 最近一次在位置 ii 结尾,且 diffu=difflinku\mathrm{diff}_u = \mathrm{diff}_{\mathrm{link}_u},则 linku\mathrm{link}_u 在 ii 之前(严格早于 ii)的最近一次出现,结尾于位置 i−diffui - \mathrm{diff}_u。

    假设当前处理到位置 ii,沿着 slink 处理每一个 Series 的贡献。设当前节点为 uu,则 uu 所在 Series 中最短回文串长度为 diffu+lenslinku\mathrm{diff}_u + \mathrm{len}_{\mathrm{slink}_u},除了最短回文串的其他贡献,恰好等于在位置 i−diffui - \mathrm{diff}_u 时已经维护好的 glinkug_{\mathrm{link}_u}。因此有转移:

    gu={fi−diffu−lenslinkudiffu≠difflinkufi−diffu−lenslinku⊕glinkudiffu=difflinkug_u = \begin{cases} f_{i - \mathrm{diff}_u - \mathrm{len}_{\mathrm{slink}_u}} & \mathrm{diff}_u \neq \mathrm{diff}_{\mathrm{link}_u} \\ f_{i - \mathrm{diff}_u - \mathrm{len}_{\mathrm{slink}_u}} \oplus g_{\mathrm{link}_u} & \mathrm{diff}_u = \mathrm{diff}_{\mathrm{link}_u} \end{cases}

    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;
        }
    }