随机说话 3

· · 个人记录

约定:

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) 段等差数列。