浅谈KMP算法（c++）

为方便讲述，字符串下标从 开始

前缀函数

给定一个长度为$n$的字符串$s$其前缀函数定义为一个长度为$n$的数组 $\pi$,${\pi }_i$ 为子串$s[0,1,\dots \dots i]$的所有相等的真前缀和真后缀（称为border）的最长长度，若没有则为.
朴素求解前缀函数

int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
for (int j = i; j >= 0; j--)
if (s.substr(0, j) == s.substr(i - j + 1, j)) {pi[i] = j;break;
}

这显然是一个$n^3$的算法
我们可以通过一些观察来优化这个算法。

1. ${\pi }_{i+1}\le {\pi }_i+1$ 反证即可，假设${\pi }_{i+1}$更大，那${\pi }_i$也应该更大
   通过这个我们可以把原来的暴力优化成 但这还不够优秀
2. 如果失配，我们可以利用之前已经处理过的信息来避免一些重复比较
   考虑我们当前已经处理完前$i$为，且第$i+1$位失配，即$s_i\ne s_{{\pi }_i+1}$，我们想快速找到最长的新匹配。
   由 border 的定义，也就是我们要找到最大的j使得$s_{i,j}=s_{i=j+1,i}$^$s_{j+1}=s_{i+1}$
   只考虑第一个条件，事实上$j={\pi }_{{\pi }_i}$
   证明：
3. ${\pi }_{{\pi }_i}$满足条件1 ，手模一下即可。
4. ${\pi }_{{\pi }_i}$是最大的满足条件的，反证即可。
   通过以上两个观察，我们就可以得出最终的算法，也就是 KMP

for(int i = 2, j = 0; i <= n; ++i){
while(j && s[j + 1] != s[i])j = nxt[j];
if(s[j + 1] == s[i]) ++j;
nxt[i] = j;
}

时间复杂度由 while 循环计算，复杂度$O(n)$

应用

字符串匹配

【模板】KMP

题目描述

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

输入格式

第一行为一个字符串，即为 $s_1$。
第二行为一个字符串，即为 $s_2$。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。
最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

样例 #1

样例输入 #1

ABABABC
ABA

样例输出 #1

1
3
0 0 1

提示

样例 1 解释

。

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

• Subtask 1（30 points）：$|s_1|\le 15$，$|s_2|\le 5$。
• Subtask 2（40 points）：$|s_1|\le 10^4$，$|s_2|\le 10^2$。
• Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $1\le |s_1|,|s_2|\le 10^6$，$s_1,s_2$ 中均只含大写英文字母。

思路

对模式串跑 KMP，得到 数组ne，然后直接扫文本串匹配即可，若失配则跳 ，完全匹配时也跳 ，因为有可能两次出现有重叠的部分。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,i,j;
char  p[N],s[N];
int ne[N];
int main(){scanf("%s%s",s+1,p+1);m=strlen(s+1);n=strlen(p+1);for(i=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}for(i=1,j=0;i<=m;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==n){printf("%d\n",i-n+1);j=ne[j];}}for(int i=1;i<=n;i++)printf("%d ",ne[i]);
}

本质不同子串数

给定长度为$n$的字符串$s，求本质不同子串数。考虑用递推的方法，令$$f_i$为$s[1,i]$的本质不同子串数，考虑如何算出$f_{i+1}$新出现的子串显然只能是以$i+1$结尾的。
如果将字符串反转，就变成要计数以$i+1$开头且未出现过的子串。
我们可以反过来计数已经出现过的有多少个，考虑我们前缀函数求出了什么，每一个border都是一个以$i+1$开头的子串的出现。
所以出现过的一共有${\pi }_{max}$个，新增的就是$i+1-{\pi }_{max}$
这样我们就可以以$O(2)$的复杂度求出本质不同子串数。
当然，还有更复杂的算法可以用更优秀的复杂度处理该问题，在此不表。

例题讲解

[NOI2014] 动物园

题目描述

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解 KMP 算法。

园长：“对于一个字符串 $S$，它的长度为 $L$。我们可以在 $O(L)$ 的时间内，求出一个名为 $\mathrm{next}$ 的数组。有谁预习了 $\mathrm{next}$ 数组的含义吗？”

熊猫：“对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 $\mathrm{next}[i]$。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例 $S$ 为 $\text{abcababc}$，则 $\mathrm{next}[5]=2$。因为$S$的前$5$个字符为 $\text{abcab}$，$\text{ab}$ 既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出 $\mathrm{next}[1]=\mathrm{next}[2]=\mathrm{next}[3]=0$，$\mathrm{next}[4]=\mathrm{next}[6]=1$，$\mathrm{next}[7]=2$，$\mathrm{next}[8]=3$。”

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在 $O(L)$ 的时间内求出 $\mathrm{next}$ 数组。

下课前，园长提出了一个问题：“KMP 算法只能求出 $\mathrm{next}$ 数组。我现在希望求出一个更强大 $\mathrm{num}$ 数组一一对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $\mathrm{num}[i]$。例如 $S$ 为 $\text{aaaaa}$，则 $\mathrm{num}[4]=2$。这是因为$S$的前 $4$ 个字符为 $\text{aaaa}$，其中 $\text{a}$ 和 $\text{aa}$ 都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而 $\text{aaa}$ 虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，$\mathrm{num}[1]=0,\mathrm{num}[2]=\mathrm{num}[3]=1,\mathrm{num}[5]=2$。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出$\mathrm{num}$数组呢？

特别地，为了避免大量的输出，你不需要输出 $\mathrm{num}[i]$ 分别是多少，你只需要输出所有 $(\mathrm{num}[i]+1)$ 的乘积，对 $10^9+7$ 取模的结果即可。

输入格式

第 $1$ 行仅包含一个正整数 $n$，表示测试数据的组数。
随后 $n$ 行，每行描述一组测试数据。每组测试数据仅含有一个字符串 $S$，$S$ 的定义详见题目描述。数据保证 $S$ 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

输出格式

包含 $n$ 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 $10^9+7$ 取模的结果。输出文件中不应包含多余的空行。

样例 #1

样例输入 #1

3
aaaaa
ab
abcababc

样例输出 #1

36
1
32

提示

测试点编号	约定
1	$n\le 5,L\le 50$
2	$n\le 5,L\le 200$
3	$n\le 5,L\le 200$
4	$n\le 5,L\le 10,000$
5	$n\le 5,L\le 10,000$
6	$n\le 5,L\le 100,000$
7	$n\le 5,L\le 200,000$
8	$n\le 5,L\le 500,000$
9	$n\le 5,L\le 1,000,000$
10	$n\le 5,L\le 1,000,000$

思路

要求的就是每个前缀的 border 集合大小，并且满足这个 border 得是不大于字符串长度一半的。
首先给出一种暴力的做法，对于每一个前缀$s[1:j]$都不断跳 next 指针，如果当前跳到$i$的节点 满足其长度不超过$\frac{j}{2}$ 那么就给$nu{m}_j$加上1 。这个算法成立的原因是 border 的传递性：不断迭代 next 等价于遍历 border。
集合大小可以通过跳 next 的次数得到，也就是说我们可以记录一下从每个串出发不断跳next，能跳多少次，计为$cn{t}_i$ ，那么有$cn{t}_i=cn{t}_{nex{t}_i}+1$ 。其实也可以将$(i,nex{t}_i)$建成一棵树，这棵树常被称为$border$树或是$$fail$树。树上的深度也就代表着对应节点的 $border$个数。
于是问题可以转化为对于每个$s[1:i]$求满足条件的最长的 border s[1;j]，之后给答案累乘上$cn{t}_j+1$即可。
至于如何去求这个$j$，首先给出一种基于分析的做法：
如果我们已经求出了$s[1:i]$ 的$j$ ，在这个基础上去求$s[1:i+1]$ 的满足条件的$k$ 。
直觉告诉我们，用与求 next 指针一样的方法去做就好了：不断去检查$s_{j+1}$ 是否与$s_{i+1}$相等。如果是那么$k=j+1$，否则令$j=nex{t}_j$并继续检测相等的过程。特别的，
最终如果发现$k>\frac{i+1}{2}$，那么令$k=nex{t}_k$。
根据与求 next 过程类似的分析可以发现，这个过程求出的 j 一定是一个合法的 border。
但是为什么一定是最大的？可以通过反证法证明，直接理解也并不困难。
另外给出一种看起来就很套路的做法：
问题可以转换到 border 树上。那么只需要对于每个前缀s[1 : i]求出border 树上 i 的祖先中长度满足条件$<\frac{i}{2}$ 的第一个并给答案累乘它的深度。
可以通过倍增来求解。预处理出$Nex{t}_{x,i}$表示从s[1 : x]跳 $2^i$次 next 指针会跳到哪个节点。
对于每次询问i从大到小枚举二进制位，如果跳完之后还不满足$<\frac{i}{2}$ 就不断跳。这个过程与倍增求 lca 类似。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
char s[1000100];
int f[1000100], num[1000100];
int main() {int T;scanf("%d", &T);while (T--) {scanf("%s", s + 1);int n = strlen(s + 1);f[1] = 0;num[1] = 1;for (int i = 2, j = 0; i <= n; ++i) {	while (j && s[j + 1] != s[i]) j = f[j];if (s[j + 1] == s[i])f[i] = ++j;elsef[i] = 0;num[i] = num[j] + 1;}long long ans = 1;for (int i = 2, j = 0; i <= n; ++i) {while (j && s[j + 1] != s[i]) j = f[j];if (s[j + 1] == s[i]) ++j;if (j > i >> 1) j = f[j];ans = (ans * (num[j] + 1)) % mod;}printf("%lld\n", ans);}return 0;
}

[POI2006] OKR-Periods of Words

题面翻译

对于一个仅含小写字母的字符串 $a$，$p$ 为 $a$ 的前缀且 $p\ne a$，那么我们称 $p$ 为 $a$ 的 proper 前缀。

规定字符串 $Q$ 表示 $a$ 的周期，当且仅当 $Q$ 是 $a$ 的 proper 前缀且 $a$ 是 $Q+Q$ 的前缀。若这样的字符串不存在，则 $a$ 的周期为空串。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

题目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

输入格式

In the first line of the standard input there is one integer $k$ ($1\le k\le 1000000$) - the length of the string. In the following line a sequence of exactly $k$ lower-case letters of the English alphabet is written - the string.

输出格式

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

样例 #1

样例输入 #1

8
babababa

样例输出 #1

24

思路

根据 border 与周期的关系，我们知道我们要求的就是每个前缀的最小 border。
对于S[1 : i] ，如果其最小的 border j满足$i-j\ge \frac{i}{2}$ ，就可以为答案累计 。
根据迭代 next 遍历 border 集合的原理，我们可以对每个前缀s[1 : i]维护一个$m{n}_i$表示由i不断跳 next 所能得到的最小的非 0 border。
容易发现如果 $nex{t}_i=0$，那么$m{n}_i=i$ ，否则$m{n}_i=m{n}_{nex{t}_i}$ 。
另外如果把本题放到 border 树上，可以发现这个要求的东西就是每个节点属于根节点（长度为 0 的前缀）的哪个子树。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long n,i,j;
char s[N];
long long ne[N],ans;
int main(){scanf("%d%s",&n,s+1);for(i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1])j=ne[j];if(s[i]==s[j+1])j++;ne[i]=j;}for(i=2,j=2;i<=n;i++,j=i){while(ne[j])j=ne[j];if(ne[i])ne[i]=j;ans+=i-j;}cout<<ans<<endl;
}

[BOI2009] Radio Transmission 无线传输

题目描述

给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\text{abc}$ 不断自我连接得到 $\text{abcabcabcabc}$，读入的 $\text{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1<L\le 10^6$。

思路

本题考查的是对next数组的理解，其实答案就是n-ne[n]

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,i,j;
char  p[N],s[N];
int ne[N];
int main(){scanf("%d%s",&n,p+1);for(i=2,j=0;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}printf("%d\n",n-ne[n]);
}

[COCI2011-2012#4] KRIPTOGRAM

题目描述

现有一段明文和一部分密文。明文和密文都由英文单词组成，且密文中的一个单词必然对应着明文中的一个单词。

求给出的密文在明文中可能出现的最早位置。

输入格式

第一行，若干个英文单词和一个 $\texttt $$，表示明文。

第二行，若干个英文单词和一个 $\texttt $$，表示密文。

每行末尾的 $\texttt $$ 用于表示该行结束。数据保证没有多个 $\texttt $$ 出现在同一行的情况。

输出格式

输出密文在明文中可能出现的最早位置，即密文的第一个单词在明文中可能出现的最早位置。

样例 #1

样例输入 #1

a a a b c d a b c $
x y $

样例输出 #1

3

样例 #2

样例输入 #2

xyz abc abc xyz $
abc abc $

样例输出 #2

2

样例 #3

样例输入 #3

a b c x c z z a b c $
prvi dr prvi tr tr x $

样例输出 #3

3

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，明文和密文所对应字符串的长度不超过 $10^6$，输入的单词均由小写字母组成。

【提示与说明】

题目译自 COCI 2011-2012 CONTEST #4 Task 6 KRIPTOGRAM。

本题分值按 COCI 原题设置，满分 $140$。

思路

在传统的 KMP 算法中，我们直接比较字符之间是否相等。

针对此题的情况，只需要把判断式换成i - preA[i]== j - preB[j] || ! preB[j] && preA[i] <= i - j就行

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
string a[N], b[N];
int lena, lenb;
int sp_len[N], prea[N], preb[N];
void getPre(string str[], int pre[], int length) {unordered_map<string, int> last_pos;for (int i=1;i<=length;i++) {pre[i]=last_pos[str[i]];last_pos[str[i]]=i;}
}
void getSpLen() {int i=2,j=1;while (i<=lenb) {if(i-preb[i]==j-preb[j]||!preb[j]&&preb[i]<=i-j)sp_len[i++]=j++;else if(j>1)j=sp_len[j-1]+1;else i++;}
}
int main() {string x;while (cin>>x,x!="$")a[++lena]=x;while (cin>>x,x!="$")b[++lenb]=x;getPre(a,prea,lena);getPre(b,preb,lenb);getSpLen();int i=1,j=1;while (i<=lena) {if(i-prea[i]==j-preb[j]||!preb[j]&&prea[i]<=i-j)i++, j++;else if(j>1)j=sp_len[j-1]+1;else i++;if(j>lenb){cout<<i-lenb<<endl;return 0;}}cout<<-1<<endl;return 0;
}

这是我的第十九篇文章，如有纰漏也请各位大佬指正
辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。