Border 理论

szt100309 · 2025-03-15 15:14:46 · 个人记录

定义

若 S' 同时为 S 的前缀和后缀，且 S'\ne [\mathbb\emptyset],S'\ne S，则 S' 为 S 的 \text{Border}（\text{Border} 为一个字符串，但有时也指代其长度）

令 \mathcal B(S) 为 S 的 \text{Border} 集合

对于 k\in\mathbb N,k<|S|，若 \forall i>k,S_i=S_{i-k}，则 k 为 S 的周期（\operatorname{Period}）（周期为正整数）。若 k 为 |S| 的因数，则 k 为 S 的整周期

令 \mathcal P(S) 为 S 的周期集合

定理 1：若 t 为 S 最长 \text{Border}，则 \mathcal B(S)=\mathcal B(t)\cup\{t\}

定理 2：t\in\mathcal B(S)\iff |S|-|t|\in \mathcal P(S)

前缀数组

定义

对于 S，令 n=|S|，定义其前缀数组 \pi_i 为 \operatorname{prf}(S,i) 的最长 \text{Border} 长度

也称为前缀函数

模板

// 前缀函数
template <typename value_t, typename output_iter_t, ass_is_RAI(output_iter_t)>
    void prefix_function(const basic_string<value_t> &s, output_iter_t pi){//[0,pi_i)=[i-pi_i,i)
        if (s.empty())return;
        size_t n = s.size();
        *pi = 0;
        for (size_t i = 1, j = 0; i != n; ++i){
            while (j && s[i] != s[j])j = pi[j - 1];
            if (s[i] == s[j])++j;
            pi[i] = j;
        }
    }

时间复杂度 O(n)

KMP 算法

全称为 \text{Knuth–Morris–Pratt} 算法，是一种单模式串字符串匹配算法

模板：

// KMP 算法
template <typename value_t, typename output_iter_t, ass_is_RAI(output_iter_t)>
    vector<size_t> kmp(const basic_string<value_t> &text, const basic_string<value_t> &pat, output_iter_t pi){//返回匹配位置
        if (text.size() < pat.size())return {};
        if (text.size() == pat.size()){if (text == pat)return {0};return {};}
        if (pat.empty())return {};
        prefix_function(pat, pi);
        size_t n = text.size(), m = pat.size();
        vector<size_t> ret;
        for (size_t i = 0, j = 0; i != n; ++i){
            while (j && text[i] != pat[j])j = pi[j - 1];
            if (text[i] == pat[j])++j;//[i-m+1,i]=[0,j)
            if (j == m)ret.emplace_back(i - m + 1), j = pi[j];
        }
        return ret;
    }

时间复杂度 O(n+m)

失配树

建立 n+1 个点，编号 0\sim n，依次表示长为 n 的字符串 S 的每个前缀

对于 1\le i\le n，i 向 \pi_i 连有向边，则构成一棵以 0 为根的内向树，称为失配树

对于 S 的每个前缀，其 \text{Border} 集合为它在树上所有非根祖先（不含自身）

例：CF1286E Fedya the Potter Strikes Back

给定 s_{1\sim n} 和 w_{1\sim n}，对于每个 1\le i\le n，求出 \sum_{s[L:R]=s[1,R-L+1],R\le i}\min_{j=L}^R w_j，强制在线（即每次只给出一组 (s_i,w_i)），n\le6\times10^5

显然长度为 i 时的答案等于长度 i-1 时的答案 加上 \sum_{s[L:i]=s[1,i-L+1]}\min_{i=L}^i w_i，考虑计算之

这等于 \sum_{s'\in\mathcal B(\operatorname{prf}(s,i))}\min_{k=i-|s'|+1}^i w_k

令 \min_{k=a}^i w_k=Sw(a)，使用单调栈 或 \operatorname{ST} 表 维护之，做到 O(\log n)（单调栈上二分）或 O(1)（\operatorname{ST} 表）查询

转化为求解 \sum_{s'\in\mathcal B(\operatorname{prf}(s,i))}Sw(i-|s'|+1)

令 Bp(S,i)=\{i-|s'|+1\mid s'\in \mathcal B(S)\}

则转化为求 \sum_{l\in Bp(\operatorname{prf}(s,i))}Sw(l)

考虑维护集合 R^\ast =\{Sw(l)\mid l\in Bp(\operatorname{prf}(s,i))\}

先考虑从 Bp(\operatorname{prf}(s,i-1)) 到 Bp(\operatorname{prf}(s,i)) 的变化

若 s_i=s_1，则 Bp(\operatorname{prf}(s,i)) 会在 Bp(\operatorname{prf}(s,i-1)) 的基础上加入 i（显然加入 R^\ast 的最多只有这一个）

然后从中删去不再合法的部分，即集合 Bp(\operatorname{prf}(s,i-1))-Bp(\operatorname{prf}(s,i))

维护数组 fadf_i，表示最大的 l 使得 s_{l+1}\ne s_{i+1}，且 l\in\mathcal B(i)

显然得到 s_i 后可以 O(1) 求出 fadf_{i-1}，且 fadf_1\sim fadf_{i-2} 不再改变

令 pi_i 为 s 的前缀数组

这样可以均摊 O(1) 找到所有满足要求的 l

此时已经可以在可接受复杂度内维护 Bp(\operatorname{prf}(s,i)) 了，考虑如何维护 \sum_{l\in Bp(\operatorname{prf}(s,i))}Sw(l)，这等价于维护 R^\ast 的元素和

对于集合 Bp(\operatorname{prf}(s,i))，操作只有加入和删除两种，因此 R^\ast 需要支持插入、删除、对给定数取 \min，查询总和，可以用 std::map 均摊 O(\log n) 维护上述操作

总时间复杂度 O(n\log n)

代码

弱周期引理 与 周期引理

弱周期引理：

定理 3：若 t 是 s 的前缀，且 a\in \mathcal P(s), b\in\mathcal P(t), b\mid a, |t|\ge a，且 b 是 t 的整周期，则有 b \in \mathcal{P}(s)

周期引理

其他常用定理

定理 4：若 s 在 t 中匹配了多次，且 |t|\ge \frac{|s|}2，则每次匹配的位置形成一个公差为 s 的最小周期长度的等差数列

例：CF1038F Wrap Around

给定 0/1 字符串 s，求有多少长为 n 的字符串 t，满足 t^{\infty}（表示以 t 为循环节的无限循环字符串）包含 s，|s|\le n\le40，加强到 4000

使用定理 4 的方法

由于 |s|\le n，显然 s 为 t 的子串，或 s 的前缀为 t 的后缀且 s 剩余部分为 t 的前缀

对于某个 t，若令 f_i 表示 t 从 i 开始长为 |s| 的子串（超过 m 则从头开始）是否与 s 相同，则 t 合法等价于 f 中至少有一个 1

考虑容斥，令 p_x=\sum_{|S|=x}|\{f|\forall i\in S,f_i=1\}|，则答案为 \sum_{i=1}^n(-1)^{i+1}p_i

若一个 t 合法，则其所有循环同构串都合法，因此只统计 f_1=1 的 t 以避免重复

一个 f_1=1 的 t 对应 n-y+1 个合法的 t，其中 y 为最后一个 f_i=1 的 i

令 dp_{i,j,k} 为当前填到 t_i，1\sim i 中 f_i 最后一个为 1 的位置为 j，f_i 中 1 的数量至少为 k

令 g_i 表示 s 是否有长为 m-i 的 \text{Border}

若令 f_i=1，则 dp_{i-1,x,k-1}\rightarrow dp_{i,i,k}。此时若有 x+m<i，则要求 s 有长 m-(i-x) 的 \text{border}，否则会与之前填的矛盾；若有 i+m-1>n，则要求 s 有长为 m-(n-i+1) 的 \text{border}，否则会和前缀的 f 矛盾

若令 f_i=0，则有两种情况：

• 若 i<x+m，则当前位置的 t 被最后一个 f 限制，只有一种取值，f_{i-1,x,k}\rightarrow f_{i,x,k}
• 否则可以填 0/1（由于 dp 值的定义为至少，因此这里不用考虑新产生 f_i=1 的情况），2f_{i-1,x,k}\rightarrow f_{i,x,k}

时间复杂度 O(n^3)

发现最后一维 k 在容斥中只需要其奇偶性，因此 k 可以只取 0/1，时间复杂度降为 O(n^2)。dp 第一维可以滚动数组优化，空间复杂度 O(n)

代码

定理 5：字符串 s 所有长度不小于 \frac{|s|}2 的 \text{Border} 长度构成等差数列

定理 6：字符串所有 \text{Border} 长度排序后可以划分成 \lceil\log_2|s|\rceil 个连续段，使得每段都为等差数列

例：P4156 [WC2016] 论战捆竹竿

给定长为 n 的字符串 s，定义拼接为将一个 s 的后缀（可以为全部）接在另一个 s 之后，满足前者剩余的前缀为后者的后缀，求将若干 s 拼接后可以到达的不超过 w 的长度数量，w\le10^{18},n\le5\times10^5，多测 T\le5

令 a_{1\sim ct} 为 \mathcal P(s) 从小到大排序的结果，则题目等价于求 [0,w-n] 中可以表示为 \sum_{i=1}^{ct} a_i x_i 的数量，其中 x_i\in\mathbb N

按一般的同余最短路，定义 f_i\;(0\le i< a_1) 为走到任意 \bmod a_1=i 的位置经过的最小长度，则答案为

按这样直接计算为 O(n\cdot ct\cdot \log n)=O(n^2\log n) 的

用 (F,D,C) 表示首项为 F，公差为 D，末项为 F+DC 的等差数列

发现 [0,F) 内的不同模 \gcd(F,D) 同余类之间不存在转移，因此分别考虑，以下只考虑其中一个同余类

令 p 为当前同余类中 f' 最小值的下标

显然在上述转移过程中，f_p=f'_p，且不存在跨越 p 的最优跟新（跨越 p 定义为 j<p<i，或 p<i<j，或 i<j<p）（j 跟新 i 定义为 j 使 f_i 的值严格变小）（若存在跨越的，则令 j=p，一定不劣于跨越的 j）

因此从 p 开始处理这个同余类

此时转移方程变为滑动窗口的形式，单调队列解决即可

对于第二个问题，设 f' 为模数跟新为 NewMd 后的 f 数组，f 为未跟新时的数组，Nwmd 为跟新前模数，则

同样各个模 \gcd(Nwmd,NewMd) 同余类分开处理

形式类似第一个问题的 dp，但滑动窗口变为前缀，直接计算即可

时间复杂度 O(\sum n\log n)，常数极大

代码（其中的 hash 判断是为了过 \text{UOJ} 的 \text {Extra Test}）

定理 7：回文串的回文前 / 后缀即为其 \text{Border}

由此可推出一个字符串所有 \text{Border} 按长度从大到小排序，其中回文的恰好为一个可空后缀，即 fail 树上回文的串为包含根的连通块或不存在

定理 8：若回文串 S 有周期 p，则可以把 \operatorname{prf}(S,p) 划分成长度为 |S|\bmod p 的前缀和长度为 p-|S|\bmod p 的后缀，使得它们都是回文串

定理 9：若 B 是回文串 S 的最长 \text{Border} 且 |B| \ge \frac{|S|}{2}，则 B 在 S 中恰能匹配 2 次

重要后缀（Significant Suffixes）

令 \operatorname{Ssf}(S) 为在 S 后接一个字符串（可以为空）后可能成为 S 的最小后缀的后缀集合

定理 10：对于任意字符串 S 及 u, v\in \text{Ssf}(S),|u|<|v|，有 u 是 v 的 \text{Border}

定理 11：对于任意字符串 S 及 u, v\in\text{Ssf}(S),|u|<|v|，有 2|u|\le|v|

定理 12：|\text{Ssf}(s)| \le \log_2|s|

例：P5211 [ZJOI2017] 字符串

长为 n 的序列，q 次操作，区间加减或区间查询字典序最小后缀起始位置（仅保留该区间的情况下），n\le2\times10^5,q\le3\times10^4

线段树维护序列，每个节点保存对应区间内的 \text{Ssf} 集合

可证父区间的 \text{Ssf} 一定为两子区间的 \text{Ssf} 的并的子集

因此合并区间时，暴力枚举儿子的每个后缀，判断是否是父亲的 \text{Ssf} 即可

需要使用分块哈希的方式维护原串，做到单次 O(1) 比较后缀

时间复杂度 O(n\log^2 n+m\log^3 n+m\sqrt n)

代码

参考

1. Border 理论小记