DDOSvoid's Blog

KMP

发表于 更新于 分类于
本文字数： 4.5k 阅读时长 ≈ 4 分钟

KMP

模板

简单来讲，$KMP$ 算法大概分成两部分

  1. 求 $nxt$ 数组
  2. 匹配

首先，$nxt$ 数组的定义为 $pre[i]$ 的最长的一段真前缀，满足这个真前缀同时是 $pre[i]$ 的后缀，或者说是最长的 $border$

匹配的话，大概的思想就是如果我们已经匹配 $i$ 位之后失配，说明之前 $i$ 位是匹配的

那么我们在失配后可以直接取 $pre[i]$ 最长的 $border$ 来进行匹配，也就是 $nxt$ 数组记录的东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int nxt[maxn]; 
void init_nxt(char *s) {
    int k = 0, l = strlen(s + 1); nxt[1] = 0; 
    for (int i = 2; i <= l; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k;
    }
}

void kmp(char *s, char *t) {
    int k = 0, l1 = strlen(s + 1), l2 = strlen(t + 1); 
    for (int i = 1; i <= l1; ++i) {
        while (k && s[i] != t[k + 1]) k = nxt[k];
        if (t[k + 1] == s[i]) ++k;
        if (k == l2) cout << i - k + 1 << "\n";
    }
}

失配树

简单来讲就是 $nxt[i]$ 连 $i$，根是 $0$

几个性质

  1. $u$ 的子树为 $pre[u]$ 在原串中的所有匹配位置（结束位置
  2. 从 $u$ 到根的所有节点为 $pre[u]$ 的所有 $border$

扩展KMP

模板

大概就是求两个东西：

  1. 字符串 $s$ 的每个后缀和 $s$ 的 $lcp$
  2. 字符串 $t$ 的每个后缀和 $s$ 的 $lcp$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int z[maxn];
void init_Z(char *s) {
    int n = strlen(s + 1); z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; ++i) {
        z[i] = i <= r ? min(z[i - l + 1], r - i + 1) : 0;
        while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

int p[maxn];
void exkmp(char *s, char *t) {
    int n = strlen(s + 1), m = strlen(t + 1); init_Z(t);
    for (int i = 1, l = 0, r = 0; i <= n; ++i) {
        if (i <= r) p[i] = min(z[i - l + 1], r - i + 1);
        while (i + p[i] <= n && s[i + p[i]] == t[p[i] + 1]) ++p[i];
        if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
}

应用

  1. 求字符串 $S$ 的最小周期

    $n-nxt[n]$ 即为最小周期

  2. 求 $pre(S,i)$ 在 $S$ 中的前缀重复出现次数

    $\lfloor \frac{z[i+1]}{i}\rfloor+1$

  3. 求 $S$ 的每个前缀串在 $S$ 中的出现次数

例题

  1. 简要题意：给定字符串 $S$ 和 $k$，$len(S)=n$，对于所有 $i\in[1,n]$，求 $pre(S,i)$ 是否可以被表示成 $ABAB\cdots A$ 的形式，其中 $A$ 出现 $k+1$ 次，$B$ 出现 $k$​ 次，$A$ 和 $B$ 都可以是空串

    $n,k\le 10^6$

    简要题解：我们注意到 $AB$ 的一定是由 $per(S)$​ 组成的，因为 $A$ 是 $AB$ 的前缀，令 $d=\lfloor\frac{len(S)}{per(S)}\rfloor$，则 $AB$ 的长度只能是 $\lfloor\frac{d}{k}\rfloor$

    如果 $S\equiv 0(\bmod per(S))$，那么我们只需要满足 $\lfloor\frac{d}{k}\rfloor\ge d\bmod k$，否则必须满足 $\lfloor\frac{d}{k}\rfloor> d\bmod k$，因为 $S$ 分成 $d$ 块之后还剩一个小于 $d$ 的块

    求完 $nxt$ 数组后，对于 $S$​ 的每个前缀判断即可，时间复杂度 $O(n)$

    CF 526D Om Nom and Necklace

  2. 简要题意：给定 $n$ 个字符串，现在要合并这 $n$ 个字符串，对于第 $i$ 个加入的字符串，我们会删掉这个字符串的最长的一个和前 $i-1$​ 个已经合并好的字符串的后缀相等的前缀，求最后合并好的字符串

    $n\le 10^5,len\le 10^6$

    简要题解：我们发现这个东西有点像是 $border$​，我们考虑将两个串都翻转一下，发现正好是求 $border$

    注意到这个 $border$​ 不能超过第一个串的长度，我们在两个串之间加一个特殊字符即可避免，时间复杂度 $O(len)$

    CF 1200E Compress Words

  3. 简要题意：给定一个字符串 $S$，求 $S$ 的所有合法的 拆分方案，$S$ 的一个拆分我们定义为 $S=(AB)^kC$，其中 $A,B,C$ 均为非空字符串，且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量，$k$ 为正整数，两个方案不同当且仅当 $A,B,C$ 至少一个字符不同

    $T\le 5,S\le 2^{20}$​

    简要题解：我们考虑枚举 $AB$ 的长度然后枚举重复出现次数，用 $hash$ 来判断，用树状数组维护 $A$ 的贡献，这样的时间复杂度是 $O(Tn\log n\log 26)$​，不足以通过此题

    我们发现对于固定的 $AB$，出现次数只有奇数和偶数两种情况，那么现在的瓶颈在于如何快速得到出现次数，我们考虑借助扩展 $KMP$ 的 $z$ 数组，容易得到 $per(S,i)$ 的前缀重复出现次数为 $\lfloor \frac{z[i+1]}{i}\rfloor+1$

    时间复杂度 $O(Tn\log 26)$，好像有严格 $O(Tn)$ 的做法

    Luogu P7114 [NOIP2020] 字符串匹配

  4. 简要题意：给定字符串 $S$​ 和 $m$​，接下来有 $m$​ 次询问，每次求 $S[l\cdots r]$​ 的最短循环节长度，这里的循环节的定义为如果 $t$​ 是 $S$​ 的循环节，则 $S$​ 由 $t$​ 重复若干次得到

    $n\le 5\times 10^5,m\le 10^6$

    简要题解：我们考虑每次询问暴力枚举约数 $d$，我们知道当 $n=5\times 10^5$ 时 $max_{i=1}^n\tau(i)=200$，这还算是能够接受的

    那么我们如何判断 $S[l\cdots l+d-1]$ 是 $S[l\cdots r]$ 的循环节呢，注意到如果 $S[l\cdots r-d]$ 与 $S[l+d\cdots r]$ 相等的话，$S[l\cdots l+d-1]$ 一定是 $S[l\cdots r]$ 的循环节，这是个很经典的结论

    判断相等可以使用字符串 $hash$

    Luogu P3538 [POI2012]OKR-A Horrible Poem

  5. 简要题意：给定一个字符串 $S$，例如有一个 $aba$ 的印章，我们可以用这个印章完成 $ababa$ 的印刷，中间的 $a$ 被印了两次，但是同一位置上印不同字符是不行，求一个长度最小的印章

    $n\le 5\times 10^5$

    简要题解：我们考虑先用 $KMP$ 求出 $fail$ 树，容易发现印章上的字符只有可能是 $n$ 到根上的所有点 $u$，且点 $u$ 合法的条件是子树内出现的点的最大间距不超过 $u$

    那么我们考虑从根向 $n$ 进行 $dfs$，每次只保留子树内的点，同时维护最大间距，因为只有删点，所以可以使用双向链表做到 $O(1)$ 删点

    Luogu P3426 [POI2005]SZA-Template

  6. 简要题意：给定一个长度为 $n$ 的模板串 $S$ 和一个空串 $T$，现在有 $m$ 次操作，操作有两种，第一种给定一个字符 $ch$ 和一个整数 $k$，表示在 $T$ 的后面加入 $k$ 个 $ch$；第二种操作给定一个整数 $k$，表示删掉 $T$ 末尾的 $k$ 个字符，问在操作的过程中，是否出现某一个时刻满足 $S$ 是 $T$ 的一个子串

    $n,m\le 2\times 10^5,k\le 10^9$

    简要题解：我们考虑建出 $S$ 的 $nxt$ 树，我们的第一想法是对于每个点预处理加入 $2^k$ 个字符 $ch$ 后转移到哪个点，但是这样做的时间复杂度和空间复杂度都是 $O(26n\log k)$ 的

    我们稍作思考可以发现，每个点只会有一个字符的成功转移，其它字符都会先不断跳 $nxt$ 直到一个可以成功转移的位置，那么我们对于每个点预处理每个字符不断跳 $nxt$ 的位置以及可以成功转移的字符跳 $2^k$ 步后所到达的位置即可

    对于删除，我们维护一个栈，记录每次添加字符前所在的位置，每次暴力删除即可，时间复杂度 $O(n\log k)$

    2022杭电多校2 H Keyboard Warrior

  7. 简要题意：给定一个长度为 $n$ 的排列 $p_i$ 和一个长度为 $m$ 的序列 $a_i$，对于一个长度为 $n$ 的序列 $a_i$ 和一个长度为 $n$ 的排列 $p_i$，称 $a_i$ 符合 $p_i$ 当且仅当 $a_i$ 互不相同，且将 $a_i$ 从小到大排序会得到 $a_{p_1},\cdots, a_{p_n}$，现在需要对给定的序列 $a_i$ 求其有多少个符合给定排列 $p_i$ 的长度为 $m$ 的子串

    $n\le m\le 10^6$

    简要题解：首先我们将 $p_i$ 变成 $p’_{p_i}=i$，下面以 $p$ 来代表 $p’$，那么现在的匹配规则就是将 $a_i$ 离散化后与 $p_i$ 是否对应位都相等，注意到这个东西是非常难处理的，因为一个位置的值与其前面的数和后面的数都有关系，我们考虑将每个数的值定义为其前面有多少小于它的数

    然后我们考虑求 $nxt$ 数组和 $kmp$ 的过程，我们需要动态维护对于 $a_i$ 在序列 $[nxt_{i-1},i]$ 的值，这个可以用树状数组实现，在 $nxt$ 向会跳的时候我们在树状数组上撤销这些值即可，$nxt$ 指针的移动是均摊 $O(n)$ 的，匹配时用类似的方法即可，时间复杂度 $O(n\log n)$

    Luogu P4696 [CEOI2011] Matching

  8. 简要题意：定义 $S$ 的 $k$ 子串为 $S_k=S[k..n-k+1],k\le \lceil\frac{n}{2}\rceil$，求 $S_k$ 的最长 $border$ 长度，$k\in [1,\lceil\frac{n}{2}\rceil]$

    $|S|\le 10^6$

    简要题解：令 $ans_i$ 表示 $S_i$ 的最长 $border$，容易发现 $ans_i\le ans_{i+1}+2$，画图容易验证，那么我们暴力求 $ans_i$ 即可，判断相等使用 $hash$ 即可，时间复杂度 $O(n)$

    CF 961F k-substrings