随机说话 3
stripe_python
·
·
个人记录
约定:
- 字符串拼接写作 ST,自拼接 k 次写作 S^k,无限循环写作 S^{\infty}。
- 字符集用 \Sigma 表示。不加说明时认为是 \tt{a} \sim \tt{z}。
- 字符串下标 0-indexed,写作 S[i]。
- 子串 [l,r] 用 S[l:r] 表示。前缀简写为 S[:x],后缀简写为 S[x:]。
Hash
多项式 Hash
对字符串 S,取 Hash 函数 f:S \to \mathbb{Z}_p 为
f(S)=\sum_{i=0}^n S[i] \times B^{i}
取 B>|\Sigma|,p 为大质数或 2^{64}。防止 Hack 可随机 mod 双哈希。
应用多项式 Hash 时,假定 f(S) = f(T) \iff S=T。可以配合二分求 LCP 进而比较字典序。
多项式 Hash 是半群信息,记录 (f,\text{len}) 二元组容易合并。进而得到:
性质 1(可加性)已知 f(S) 和 f(T) 可算得 f(ST)。
性质 2(可逆性)已知 f(ST) 和 f(T) 可算得 f(S)。
多项式 Hash 具备一定程度的可减性
f(S)-f(T)=\sum_{i=0}^n (S[i]-T[i]) \times B^i
Sum / Xor Hash
对字符集合 S,取映射 g: U \to \mathbb{Z}_p,定义 Hash 函数
f(S)=\sum_{x \in S} g(x)\\
f(S)=\bigoplus_{x \in S} g(x)
应用 Sum Hash 时,认为 f(S)=f(T) \iff S=T。Sum Hash 是 Abel 群。
对于映射 g,可对每个 x \in U 随机一个 [0,p) 内的整数,取 p=2^{64} 是好的。
矩阵 Hash
考虑构造一种哈希,能够区分 \tt{ab} \ne \tt{ba} 和 \tt{ab}+\tt{cd} \ne \tt{ad}+\tt{bc}。这时候 Sum Hash 或 Xor Hash 就爆了。
将每个字符映射到一个 n \times n 的随机矩阵,用矩阵乘积作为哈希值。注意到矩阵乘法没有交换律,故这种 Hash 能够区分上面的情况。
我们常常希望矩阵可逆,使得 Hash 是群信息。有下面这个自逆矩阵:
\begin{bmatrix}
a & b\\
\frac{1-a^2}{b} & -a
\end{bmatrix}
随两个数 a,b,将元素在模大质数意义下运算即可。
自动机
前缀自动机
给定字符串 S,构造 DFA,仅接受 S 的所有前缀。
拉一条链出来即可。
广义前缀自动机
给定字符串 S_1 \sim S_n,构造 DFA,仅接受 S_i 的所有前缀。
这个东西就是 Trie。
Trie 的本质是动态开点权值线段树,做线段树合并分裂都可以搞。
KMP 自动机
给定字符串 S,构造 DFA,仅接受以 S 为后缀的串。
定义前缀函数 \pi[i] 为 S[:i] 最长 border 长度,连边 i \to \pi[i] 形成 fail 树。
KMP 本质是给 Fail 树暴力挂叶子。直接跳根链,判定当前字符能否接在某个 border 里面,能的话就挂叶子。复杂度均摊线性。
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[i] != s[j+1]) j = pi[j];
if (s[i] == s[j+1]) j++;
pi[i] = j;
} // 1-indexed
KMP 自动机取最长匹配长度 i 为状态,转移函数为
i\overset{c}{\to} \left\{\begin{matrix}
i+1 & i<n\land S[i+1]=c\\
0 & i=0 \land S[1] \ne c \\
\pi(i)\overset{c}{\to} & \text{otherwise.}
\end{matrix}
\right.
其中 \text{trans}(i,c)=\text{trans}(\pi(i),c) 可理解为:
接受状态为 n,节点数 O(n),转移 O(|\Sigma|)。等价于一条链的 ACAM。
border 理论
记号:
定理 1 p \in \text{per}(S)\iff n-p \in \text{bd}(S)。
定理 2(WPL)若 p, q \in \text{per}(S) 且 p+q \le n,则 \gcd(p,q) \in \text{per}(S)。
定理 3(PL)若 p, q \in \text{per}(S) 且 p+q-\gcd(p,q) \le n,则 \gcd(p,q) \in \text{per}(S)。
定理 4 长度 \ge n/2 的 border 长度构成一个等差数列。
定理 5 \text{bd}(S) 升序排序后,可以划分为 O(\log n) 段等差数列。