Day2 字符串哈希&KMP

字符串哈希 KMP

基本

字符串哈希

理论

将一个字符串转成一个数字，可以快速比较两个字符串是否相同等。要求为：相同字符串哈希值相同，不同字符串哈希值尽量不相同。

映射方法通常采用多项式哈希方法，很像进制转换。假设字符串为 $S$ ，其哈希值为 $f (S)$ 。定义一个小的正整数 $ba se$ （比如说 $27, 131$ ），表示将 $S$ 视为 $ba se$ 进制下的数字。将字符串中涉及到的每个单独的字符 $S_i$ ，转换为一个数字 $x_i$ （比如说 $\texttt{a}$ 为 $0$ ， $\texttt{c}$ 为 $2$ ）后，用秦久韶算法把 $S$ 转换后得到的数串 $\{x_1,x_2,\dots,x_n\}$ 变成 $S$ 的哈希值：
$f(S)=(\dots((((x_1\times base)+x_2)\times base)+x_3)\times base)+\dots)\times base)+x_n$
举个例子，若 $S=\texttt{xyz}$ ，则 $f(S)=23\times base^2+24\times base+25$ 。由于 $f (S)$ 通常会很大，long long 会存不下，所以要么加上 unsigned 自然溢出，要么开一个大质数 $P$ 把 $f (S)$ 对 $P$ 取模。

如果有两个不同的字符串 $S, T$ ，在某种哈希方法中 $f (S) = f (T)$ 则称为发生了哈希冲突。哈希函数的目的就是尽可能降低发生哈希冲突的概率。如果不采用任何优化手段，当 $ba se$ 在 $[0, P)$ 中均匀随机选取，则发生哈希冲突的概率大约为 $\cfrac{l-1}{P}$ ，其中 $l=\max(|S|,|T|)$ 。

如果字符串总数大于哈希值的范围( $P$ )，由鸽巢原理可知至少有两个字符串发生哈希冲突。所以最朴素的方法就是增加 $P$ 。但根据生日悖论， $P$ 不够大时，只需要很少的字符串就很容易发生哈希冲突。以 $P=10^9+7$ 为例，当有 $10^5$ 个不同的字符串时发生哈希冲突的概率高达 $99.3263\%$ 。

解决哈希冲突的常见方法：

拉链法：用一条链把相同哈希值的元素挂在一起，查询时算出哈希值后顺着挂着的链遍历一遍查找该字符串。
开放地址法：如果先后遇到两个字符串 $S, T$ ， $f (S) = f (T)$ ，则让 $f (S)$ 保持不变， $f (T)$ 去寻找新的位置填入（比如说 $f(T)\gets f(T)+1$ 去探测）。
再哈希法：准备多个备用哈希函数，当发生冲突时，使用备用的哈希函数再次计算哈希值，直到不发生冲突后将字符串映射为该哈希值。
公共溢出法：准备一个额外的空间作为公共溢出区，当 $S$ 发生哈希冲突时，就将 $S$ 扔进公共溢出区的末尾。查询时扫描整个公共溢出区即可。
多模哈希：用多个不同的 $(ba se, P)$ 计算哈希值，当 $f(S)\ne f(T)$ 和 $g(S)\ne g(T)$ 同时成立时才判断 $S\ne T$ ，其中 $g$ 是另一个哈希函数。双哈希最为常用。

如何 $O (1)$ 得到 $S$ 的某个子串 $[l, r]$ 的哈希值？我们在计算 $f (S)$ 时多记录一下 $S$ 的前缀哈希值 $h$ ： $h_i=h_{i-1}\times base+x_i$ ，其中 $x_i$ 表示 $S_i$ 的数字形式。则 $f(S_{l\dots r})$ 即为 $h_r-h_{l-1}\times base^{r-l+1}$ 。可以提前预处理出 $ba se$ 的若干次幂。

在 OI 赛场上，建议使用不同寻常的质数作为 $P$ ，否则很有可能会被卡掉。给出一个双哈希模板：

// 假设字符串只有小写字母
#define ll long long
const int BASE1 = 27,P1 = 998244353;
const int BASE2 = 131,P2 = 1e9 + 7;
int F(char s[]) {
    int n = strlen(s + 1); ll res = 0;
    for (int i = 1;i <= n;i ++)
        (res = (res * BASE1 % P1) + s[i] - 'a') %= P1;
    return res;
}
int G(char s[]) {
    int n = strlen(s + 1); ll res = 0;
    for (int i = 1;i <= n;i ++)
        (res = (res * BASE2 % P1) + s[i] - 'a') %= P2;
    return res;
}
bool checkDifferent(char s[],char t[]) { return F(s) != F(t) || G(s) != G(t);

允许失配的匹配

给定长度为 $n$ 的文本串 $S$ 和长度为 $m$ 的模式串 $T$ 。定义 $S$ 的子串 $S^{'}$ 与 $T$ 匹配，当且仅当 $∣ S^{'} ∣ = ∣ T ∣$ 且最多有 $k$ 个位置字符不同。求能够与 $T$ 匹配的 $S^{'}$ 的个数。

$1\le n,m\le10^6$ ， $0\le k\le 5$ 。

哈希+二分。先枚举 $S$ 中所有长度为 $m$ 的子串 $S^{'}$ ，尝试与 $T$ 进行匹配。求出 $S^{'}$ 和 $T$ 的前缀哈希值 $s u m S^{'}, s u m T$ （ $S^{'}$ 的前缀哈希用 $S$ 的前缀哈希计算得到），然后二分出 $S^{'}, T$ 第一个不同的位置（如果 $sumS'_{mid}=sumT_{mid}$ 相同则往后找，否则往前找）；最终将 $S^{'}$ 和 $T$ 中二分得到的失配位置及之前的部分全部删除，继续二分下一个不同的位置。如果二分到第 $k + 1$ 轮发现仍有失配位置存在，则说明 $S^{'}$ 无法匹配 $T$ ，否则答案加一。

二分至多进行 $(n-m+1)\times k$ 轮，加上开始时计算的 $s u m S, s u m T$ 的 $O (n + m)$ ，总时间复杂度为 $O(m+kn\log m)$ 。

最长回文子串

给定长度为 $n$ 的字符串 $S$ ，求其中的最长回文子串。

$O(n\log n)$ 做法：预处理出 $S$ 正着的前缀哈希，和倒着的前缀哈希。二分回文子串长度，check 的时候枚举每个回文中心，哈希判断两侧是否相等。

$O (n)$ 做法：记 $R_i$ 表示以 $i$ 结尾的最长回文子串的长度，最终答案即为 $\max\{R_i\}\ (1\le i\le n)$ 。如果要以 $i + 1$ 作为结尾，那么最优的 $R_{i+1}$ 即为：从以 $i$ 结尾的最长回文子串的前一个字符与这段回文子串和 $S_{i+1}$ 拼起来，组成一个长度为 $R_i+2$ 的回文子串，前提是 $S_{i+1}$ 与这个字符相同。所以有一个性质： $R_{i}\le R_{i-1}+2$ 。然后我们只需要暴力从 $R_{i-1}+2$ 开始递减，直到用哈希判出一个回文即可。

最长公共子串

给定 $m$ 个总长不超过 $n$ 的非空字符串，查找所有字符串的最长公共子串。其中 $1\le n,m\le10^6$ 。

如果存在长度为 $k$ 的最长公共子串，那么长度为 $k - 1$ 的子串也一定存在（挖掉一个字符即可）。所以可以二分这个子串的长度，check 部分即为将所有字符串中长度为 $k$ 的子串全部求一遍哈希值（前缀哈希），然后将求得的值分别放入 $n$ 个表中，最终如果这些表存在交集则该答案合法。时间复杂度 $O(n\log \cfrac{n}{m})$ 。

KMP

理论

用于计算给定一个文本串 $S$ （长串）和一个模式串 $T$ （短串），计算 $T$ 在 $S$ 中的出现次数/位置。适用于 $T$ 不变的情况。令 $n$ 为 $∣ S ∣$ ， $m$ 为 $∣ T ∣$ ，暴力很显然是 $O (nm)$ 。

暴力中其实多了很多冗余的比较。KMP 中就对 $T$ 多求了个 $n x t$ 数组， $nxt_i$ 表示 $T$ 中到 $i$ 为止的子串的真前缀和真后缀最大相同的前缀位置（而字符串中真前后缀相同的部分称为原串的一个 border）。例如模式串 $T=\texttt{aabaabc}$ ，对其计算 $nxt=\{0,1,0,1,2,3,0\}$ 。

假设 $S=\texttt{aabaaabaabaabca}$ ，则 KMP 的匹配过程即为：

$T_{1\dots5}$ 中的字符都匹配成功，但 $T_6$ 匹配失败（ $S_6=\texttt{a},T_6=\texttt{b},S_6\ne T_6$ ），根据当前已经匹配成功的字符个数 $n o w = 5$ ，移动 $T_1$ 与 $S_4$ 对齐，即 $now\gets nxt_{5}$ ，表示匹配成功的字符个数从 $5$ 变成 $2$ 。
继续匹配直到 $T_{1\dots 2}$ 都匹配成功，但 $T_3$ 失配（ $S_6=\texttt{a},T_3=\texttt{b}$ ），根据当前已经匹配成功的字符个数 $n o w = 2$ ，移动 $T_1$ 与 $S_5$ 对齐，即 $now\gets nxt_{2}$ ，表示匹配成功的字符个数从 $2$ 变成 $1$ 。
继续匹配直到 $T_{1\dots 6}$ 都匹配成功，但 $T_7$ 失配（ $S_11=\texttt{a},T_7=\texttt{c}$ ），根据当前已经匹配成功的字符个数 $n o w = 6$ ，移动 $T_1$ 与 $S_8$ 对齐，即 $now\gets nxt_{6}$ ，表示匹配成功的字符个数从 $6$ 变成 $3$ 。
继续匹配就发现匹配成功了。

综上，匹配操作即为：令 $n o w$ 表示已成功匹配的字符个数， $i$ 表示 $S$ 匹配到的位置，初始 $n o w = 0, i = 1$ ；检查 $S$ 中的当前字符和 $T_{now+1}$ 是否相同，若相同，则 $now\gets now+1,i\gets i+1$ ；否则：

如果 $now\ne 0$ ，则 $now\gets nxt_{now}$ 且 $i$ 不变；
如果 $n o w = 0$ ，则 $i\gets i+1$ 。

重复匹配直到 $n o w = ∣ T ∣$ 或 $i\ge |S|$ 。时间复杂度 $O (n)$ ，证明略。

怎么算 $n x t$ 数组呢？这相当于 $T$ 和 $T$ 自己进行匹配。逐位向后扩展，当失配时利用已经得到的 $n x t$ 跳。仍设两个变量 $n o w, i$ ，初始 $n o w = 0$ ，注意初始时 $i = 2$ ；显然 $nxt_1=0$ ；当 $T_i=T_{nxt+1}$ 时，计算 $nxt_i=now+1$ 并且 $now\gets now+1,i\gets i+1$ ；否则：

如果 $now\ne 0$ ，此时 $nxt_{now}$ 已经求出，所以 $now\gets nxt_{now}$ 。
如果 $n o w = 0$ ，则 $nxt_i=0,i\gets i+1$ 。

时间复杂度 $O (m)$ 。给出一个模板：

// 求 nxt
nxt[1] = 0;
for (int i = 2,now = 0;i <= m;nxt[i] = now,i ++) {
    while (now && T[i] != T[now + 1]) now = nxt[now];
    if (T[i] == T[now + 1]) now ++;
}
// 匹配，这里仅输出第一个匹配成功的位置（开头）
for (int i = 1,now = 0;i <= n;i ++) {
    while (now && S[i] != T[now + 1]) now = nxt[now];
    if (S[i] == T[now + 1]) now ++;
    if (now == m) {
        printf("%d",i - m + 1);
        break;
    }
}

前缀出现次数

给定长度为 $n$ 的字符串 $S$ 和长度为 $m$ 的字符串 $T$ ，统计：

每个前缀 $S_{1\dots i}$ 在 $S$ 中的出现次数。

每个前缀 $S_{1\dots i}$ 在 $T$ 中的出现次数。

在 oi-wiki 的这里，讲得非常细~~所以偷个懒~~。

题目

上午

~~因为老师没给我开所以写不了一点qwq~~

下午

优秀拆分 95pts

令 $f_i$ 表示以 $i$ 结尾的形如 $\texttt{AA}$ 的子串个数， $g_i$ 表示以 $i$ 开头的形如 $\texttt{BB}$ 的子串个数。计算方法即为：枚举每个长度为偶数的子串 $[L, R]$ ，比较 $[L, mi d]$ 和 $[mi d + 1, R]$ 的哈希值是否相同。然后枚举 $\texttt{AA,BB}$ 之间的分界线 $i$ ，贡献即为 $f_i\times g_{i+1}$ 。复杂度 $O(n^2)$ ，瓶颈在于求 $f, g$ 。

动物园

$num_i$ 其实就是求：从以 $i$ 结尾长度不超过 $\lfloor\frac{i}{2}\rfloor$ 的最长 border 开始，不断跳 $n x t$ 直到 $nxt_i=0$ 所用的次数。令 $now=nxt_i$ （ $n o w$ 合法），此时 $S[1,now]=S(i-now,i]\ \ \ (1)$ 。如果 $nxt_{now}$ 有值，那么说明
$S[1,nxt_{now}]=S(now-nxt_{now},now]\ \ \ (2)$
根据 $(1)$ 和 $(2)$ 可知
$S(i-now,i-now+nxt_{now}]=S(i-nxt_{now},i]\ \ \ (3)$
综合三者得
$S[1,nxt_{now}]=S(i-nxt_{now},i]\ \ \ (End)$
即 $nxt_{now}$ 也是 $S [1, i]$ 中的 border 之一。因为 $n x t$ 存的总是当前最长的 border，所以 $nxt_{now}$ 是 $n o w$ 后紧接着的 border，不会漏数。所以我们在求 $nxt_i$ 的时候顺便记录跳的次数 $K_{i}\gets K_{nxt_i}+1$ 。对于求得最长且合法的 border，先和求 $n x t$ 的过程一样求得最长的匹配成功的 $n o w$ ，然后再继续跳直到 $2\times now\le i$ ，此时 $n o w$ 即为所求。

Censoring S

提前算出 $T$ 的前缀哈希，开一个栈逐个往里扔 $S_i$ 并计算栈中元素的前缀哈希。如果发现栈中元素有 $∣ T ∣$ 个了就判断栈中栈顶 $∣ T ∣$ 个元素的哈希值是否和 $T$ 相同，如果相同则弹出这 $∣ T ∣$ 个元素。最后从栈底输出到栈顶即可。

SZA-Template

显然合法的印章一定是字符串中的一个 border（至少前后缀相同，这个印章才可能覆盖整个字符串），考虑 dp。设 $f_{i}$ 表示印 $[1, i]$ 这一段所需最短的印章长度。显然 $f_1=1$ 即用自己作为整个印章。转移时从自己的 border 处转移，尝试使用 border 的印章盖出自己；但因为 KMP 中求出的 $n x t$ 已经涵盖了较小的 border，所以直接从 $nxt_i$ 处转移即可。转移方程即为 $f_i\gets \min(i,f_{nxt_i})$ 。

但不是随时都可以转移的。如果想从 $nxt_i$ 处转移，最多最多就是用 $nxt_i$ 作为印章，然后在之前的一段后面加上一段 $nxt_i$ 印出 $i$ 来。即存在一个 $j$ ，使得两者使用的印章长度相同（有印章能用）且 $i-nxt_i\le j$ （印章一下盖得完）。开一个桶记录一下即可，注意 $1$ 一开始就丢进桶里。

String Compression

考虑 dp。设 $f_i$ 表示前 $i$ 个字符进行压缩的最小长度，初始化 $f_i=i+1$ 即不进行任何内部的压缩。令 $cnt_{i,j}$ 表示完全压缩 $[i, j]$ 这一段后的长度，显然这一段需要去找 $[i, j]$ 的最短循环节。所以我们按照每个 $i$ 为开头都跑一遍 KMP 求 $n x t$ 的过程（此时令 $i$ 为模式串的开头），此时求得的 $j-i+1-nxt_{j-i+1}$ 即为循环节（需要判断能否整除 $j - i + 1$ ，不能则说明不存在循环节，只能不进行内部压缩）。转移方程即为 $f_i=\min\{f_j+cnt_{j+1,i}\}\ (j < i)$ 。

// 核心代码，S 下标从 1 开始。
for (int i = 1;i <= n;i ++)
    f[i] = i + 1;
for (int i = 0;i <= n;i ++) { // i = 0 时相当于尝试直接整段压缩。
    KMP(S + i); // 跑出以 i + 1 为开头的 nxt 数组
    for (int len = 1;i + len <= n;len ++) {
        int j = i + len;
        if (len % (len - nxt[len]) == 0)    
            f[j] = min(f[j],f[i] + count(len / (len - nxt[len])) + len - nxt[len]);
        else f[j] = min(f[j],f[i] + len + 1);
        // count 表示数出十进制位数。
    }
}

说无可说

问题在于如何快速计算两个串的相似度。朴素算法有 dfs，动态规划等

用 $f (i, j)$ 表示 $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符需要多少次才能相同，则

$f(i,j)=\min\{f(i-1,j)+1,f(i,j-1)+1,f(i-1,j-1)+[A_i\ne B_j]\}$

由于 $f(i,j)\ge |i-j|$ ，考虑到操作次数不超过 $8$ ，则第二维可以改成 $\Delta i$ ，于是复杂度降为 $O(16\times |A|)$

用 $h(k,\Delta i)$ 表示使 $f(i,\Delta i)=k$ 的最大的 $i$ 。因为更大的 $i$ 可以更早匹配完

中间用 lcp 来转移，二分 hash 也能计算 lcp，复杂度降为 $O(64\times \log |A|)$ 。

这是老师上课讲的做法，相信各位都是一知半解~~反正我不大会就对了~~，所以这里讲一种相对暴力的做法。

首先 $O(n^2)$ 枚举两个 $A, B$ ，考虑暴搜算出 $A, B$ 之间的相似度，因为操作次数不会超过 $8$ 所以边搜边剪枝的复杂度不会太高。全局开一个 $an s$ 记录当前算到的最小操作次数，最后开一个桶记录对数即可。

课后

大段排骨

很像提高 1 的 第二饭堂。从 $S$ 的前后往中间扫，边扫边计算此时的前后缀哈希值，如果发现相等则说明在这之前的一段可以分出来。不断往中间靠拢即可。最后如果中间还剩下一段或 $∣ S ∣$ 为奇数则答案还要再加一。

倍增计算

首先破环成链。先用前缀和算环上任意一段中 $\texttt{A,B,C}$ 字母的数量（在链上处理），然后就可以钦定环的起点按照 $4$ 的幂次遍历整个环算答案了。

// 核心代码
// sum[i][0/1/2] 表示在链上 i 之前有几个 A/B/C。
for (int i = 1, ans = 0, pos = i;i <= m;i ++, ans = 0, pos = i) {
    for (int j = n - 1;j >= 0;j --) {
        for (int k = 0;k < 3;k ++)
            ans += (1 << (j << 1)) - sum[pos + (1 << (j << 1)) * (k + 1)][k] + sum[pos + (1 << (j << 1)) * k][k];
        	// 修改次数为：环上所有字符 - 与目标字符一样的字符数。
        pos += (1 << (j << 1)) * 3; // 往后处理
    }
    res = min(res,ans);
}

字符游戏

这回想明白辣！如果字符串字典序单调不减，那么显然删除的字符越靠后原串字典序越小（或相等）；而如果原串有一个部分字典序减小了，假设 $S_i>S_{i+1}$ ，则 $i$ 越靠前，删掉 $S_i$ 所得的字典序越小，且一定不大于其他诸如 $S_j\le S_{j+1}$ 时删掉 $S_j$ 后的字典序。

我们以 $S=\texttt{aabbaaaba}$ 为例。~~一眼盯真~~可得删除 $S_4$ 时字典序最小，因为 $S_4>S_5$ ；进一步可以发现一段连续且相同的字符中删掉任意一个，所得字典序都是不变的，所以删除 $S_3$ 后字典序也是最小的。根据一开始的结论，删掉 $S_8$ 后所得字典序就是次小的。为了方便，我们将这么得到的字符串称为一类字符串。剩下的情况中， $S [1, 2], S [5, 8]$ 中分别任意选择一个字符删去，分别得到的字典序不变。仍根据一开始的结论，得到的字典序从小至大为：删去 $S_9$ 、删去 $S [5, 8]$ 、删去 $S [1, 2]$ 。我们将这么得到的字符串称为二类字符串。一类字符串的字典序总是小于二类字符串。