引
入
引入
引入
“ SY 和 WYX 在看毛片。（几 毛 钱买到的动作 片，毛 片）
WYX 突然想回味一个片段，但是只记得台词里面有一句挺长的 “∗
∗
∗
∗
****
∗∗∗∗ ”，于是，他们找到剧本，想看 “
∗
∗
∗
∗
****
∗∗∗∗ ”在剧本中出现了几次，分别是在什么地方。
他们遇到了麻烦，这样的剧本随便就是数百万单词，数千万字母，而且 “∗
∗
∗
∗
****
∗∗∗∗ ”长度也有上千万。
为了解决这个问题，SY 发明了一个 O(N) 的字符串匹配算法，以这次的目的命名，就叫 KMP(看毛片) 算法。 ”
但是他们不知道，前人已经发明此算法：
KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作，简称 KMP 算法。
——摘自百度百科
“ 气愤的 SY 只好继续看毛片，并顺便拿了 NOIP2020提高组 CQ前十 ”
K
M
P
算
法
讲
解
KMP算法讲解
KMP算法讲解
引入里面讲的很形象了，
K
M
P
KMP
KMP 算法是用来解决字符串匹配问题的，
问题原型就是在一个大字符串
S
1
S1
S1 里找一个小字符串
S
2
S2
S2 出现了多少次。
暴力怎么做的不用我说了吧，咱们直接进入正题。
K
M
P
KMP
KMP 算法由两个子任务组成，求
S
2
S2
S2 每个前缀的最长
b
o
r
d
e
r
border
border 和 在
S
1
S1
S1 中匹配
S
2
S2
S2 。
Subtask 1 求 border（求 next ）
b
o
r
d
e
r
border
border 是 “边界” 的意思，字符串内既是前缀又是后缀（而不等于原串）的一个子串，形象地叫它为该字符串的
b
o
r
d
e
r
border
border.
例：
- abcab d abcab
SY is such a SY
上面两个字符串中加粗的地方就是该字符串的最长
b
o
r
d
e
r
border
border，字符串的
b
o
r
d
e
r
border
border 并不唯一，比如第一个字符串就还有另一个
b
o
r
d
e
r
border
border ：“ ab ”，但是不是最长的。
根据这个定义，我们可以想想怎么线性地求
S
2
S2
S2 每一个前缀的最长
b
o
r
d
e
r
border
border 的长度。
在
K
M
P
KMP
KMP 算法中，我们定义
S
S
S 第
i
i
i 个前缀的最长
b
o
r
d
e
r
border
border 的长度为
n
e
x
t
S
[
i
]
next_S[i]
nextS[i] （为什么叫 “next”，笔者也很好奇 ）
从字符串前端算起，很明显，由于
n
e
x
t
[
i
]
<
i
next[i]<i
next[i]<i，所以
n
e
x
t
[
0
]
=
n
e
x
t
[
1
]
=
0
next[0]=next[1]=0
next[0]=next[1]=0. 1
然后往后算，设当前算到的位置为
i
i
i ，
首先，如果
S
[
i
]
=
=
S
[
n
e
x
t
[
i
−
1
]
+
1
]
S[i]==S[next[i-1]+1]
S[i]==S[next[i−1]+1] ，那么
n
e
x
t
[
i
]
=
n
e
x
t
[
i
−
1
]
+
1
next[i]=next[i-1]+1
next[i]=next[i−1]+1 ，而且这是
n
e
x
t
[
i
]
next[i]
next[i] 最好的情况，可以直接完事，去求
i
+
1
i+1
i+1 了，因为如果
n
e
x
t
[
i
]
>
n
e
x
t
[
i
−
1
]
+
1
next[i] > next[i-1]+1
next[i]>next[i−1]+1 的话，
n
e
x
t
[
i
−
1
]
next[i-1]
next[i−1] 肯定可以等于
n
e
x
t
[
i
]
−
1
next[i]-1
next[i]−1.
（next[i] : #### # ####
→
\rightarrow
→ next[i-1] : #### # ###(#)）
那么否则就得找
i
−
1
i-1
i−1 的次大的
b
o
r
d
e
r
border
border ，以此类推。由于次大的
b
o
r
d
e
r
border
border 肯定满足是最大的 border 的前缀且后缀，因为：
- 该
b
o
r
d
e
r
border
border 对应最大
b
o
r
d
e
r
border
border 前缀部分的前缀：AAAA B AAAA
该
b
o
r
d
e
r
border
border 对应最大
b
o
r
d
e
r
border
border 后缀部分的后缀：AAAA B AAAA
最大
b
o
r
d
e
r
border
border 前缀部分和后缀部分显然相同：AAAA B AAAA
于是，可以充分证明，若当前的
b
o
r
d
e
r
border
border 大小为
x
x
x ，则次大的
b
o
r
d
e
r
border
border 为
n
e
x
t
[
x
]
next[x]
next[x] （前缀部分的
n
e
x
t
next
next）。
好，我们就可以处理出
S
S
S 每一个位置的
n
e
x
t
next
next 了。
那为什么它是线性的呢？我们可以隐约地意识到，每个位置的
n
e
x
t
next
next 没有向左扩展的过程，只有向右扩展，
由于
n
e
x
t
[
i
]
≤
n
e
x
t
[
i
−
1
]
+
1
next[i] ≤ next[i-1]+1
next[i]≤next[i−1]+1 ，所以整个计算过程中，
“
i
−
n
e
x
t
[
i
]
”
“ i-next[i] ”
“i−next[i]” 这个量就从来没下降过，而且除了一开始判断
“
S
[
i
]
=
=
S
[
n
e
x
t
[
i
−
1
]
+
1
]
”
“S[i]==S[next[i-1]+1]”
“S[i]==S[next[i−1]+1]” 可能使该量不变以外，找次大
b
o
r
d
e
r
border
border 的操作每次一定会使
“
i
−
n
e
x
t
[
i
]
”
“ i-next[i] ”
“i−next[i]”变大，因此它是线性的。
模板
void INIT(char *ss,int *nxt,int n) {
nxt[0] = nxt[1] = 0;
for(int i = 2;i <= n;i ++) {
int nm = nxt[i-1]; nxt[i] = 0;
while(nm && ss[nm+1] != ss[i]) nm = nxt[nm];
if(ss[nm+1] == ss[i]) nxt[i] = nm+1;
}
return ;
}Subtask 2 字符串匹配
K
M
P
KMP
KMP 算法实际上是通过求出
S
1
S1
S1 每一个位置
i
i
i 向前延伸出最长的一段，满足是
S
2
S2
S2 的前缀，如果该段长度
=
l
e
n
g
t
h
S
2
= length_{S2}
=lengthS2 ，那么
[
i
−
l
e
n
g
t
h
S
2
+
1
,
i
]
[i-length_{S2}+1\;,\;i]
[i−lengthS2+1,i] 就是
S
2
S2
S2 的一个出现位置，也就是说
K
M
P
KMP
KMP 是间接地解决了这个问题，这表明着该算法的功能可以更强大。
怎么做呢
仿照着求
n
e
x
t
next
next 的推导，我们来求这个……不妨定义它为
F
F
F 吧，设
F
[
i
]
F[i]
F[i] 为位置
i
i
i 向前延伸出最长的一段，满足是
S
2
S2
S2 的前缀的长度。
从左到右依次计算吧，首先
F
[
0
]
=
0
F[0]=0
F[0]=0. 1
接下来对于过程中的
i
i
i ，如果
S
1
[
i
]
=
=
S
2
[
F
[
i
−
1
]
+
1
]
S1[i]==S2[F[i-1]+1]
S1[i]==S2[F[i−1]+1] 那么
F
[
i
]
F[i]
F[i] 直接等于
F
[
i
−
1
]
+
1
F[i-1]+1
F[i−1]+1 完事，否则找
n
e
x
t
[
F
[
i
−
1
]
]
next[F[i-1]]
next[F[i−1]]，然后是
n
e
x
t
[
n
e
x
t
[
F
[
i
−
1
]
]
]
next[next[F[i-1]]]
next[next[F[i−1]]] ……直到后面那一位符号匹配。
这时候就会发现
n
e
x
t
[
]
next[]
next[] 有多么大的用处，因为其又是后缀又是前缀的性质，使得
i
i
i 可以正常地从
F
[
i
−
1
]
F[i-1]
F[i−1] 的一个
b
o
r
d
e
r
border
border 出转移过来。
它的复杂度和正确性都和
n
e
x
t
next
next 的证明类似，而且大多数人其实是第一部分看不懂而已，那就留给读者们一个思考空间吧（笔者要写扩展KMP了……）
模板
//这里的代码特别灵活，每个题都不一样，笔者就不贴了e
x
K
M
P
算
法
讲
解
exKMP算法讲解
exKMP算法讲解
“加了 ‘ex’前缀的算法总会变得高端一些呢 ”
前面说了，
K
M
P
KMP
KMP 算法是求 “
S
1
S1
S1 每一个位置
i
i
i 向前延伸出最长的一段，满足是
S
2
S2
S2 的前缀的长度 ” ，而扩展
K
M
P
KMP
KMP 则是求 “
S
1
S1
S1 每一个位置
i
i
i 向后延伸出最长的一段，满足是
S
2
S2
S2 的前缀的长度 ” ，即，
S
1
S1
S1 每个后缀与
S
2
S2
S2 的最长公共前缀。
该算法也有两个子任务，求
S
2
S2
S2 每个后缀和
S
2
S2
S2 本身的最长公共前缀长度 和 在
S
1
S1
S1 每个后缀中匹配
S
2
S2
S2（如上）.
Subtask 1 ···
不妨设
e
x
[
i
]
ex[i]
ex[i] 为
S
2
i
S2\;\,i
S2i 开头的后缀和
S
2
S2
S2 本身的最长公共前缀长度，然后我们开始想怎么线性求它。
首先，
e
x
[
1
]
=
l
e
n
g
t
h
S
2
ex[1]=length_{S2}
ex[1]=lengthS2，
e
x
[
2
]
ex[2]
ex[2] 可以暴力求出来。 1
接下来往后算，到了当前位置
i
i
i ，若
e
x
[
i
−
1
]
−
1
>
e
x
[
2
]
ex[i-1]-1 > ex[2]
ex[i−1]−1>ex[2] ，则
e
x
[
i
]
=
e
x
[
2
]
ex[i]=ex[2]
ex[i]=ex[2]。
因为它不能变得更长了，
如果变得更长的话，
会出问题的，
e
x
[
2
]
ex[2]
ex[2] 就可以变得更大了，因为
e
x
[
i
−
1
]
ex[i-1]
ex[i−1] 涵盖了更大范围的公共前缀，在
e
x
[
i
−
1
]
ex[i-1]
ex[i−1] 范围内都可以当作
S
2
S2
S2 开头考虑。
但是这并不能很好地衔接
i
+
1
i+1
i+1 ，因为这样一来直接进入
i
+
1
i+1
i+1 的话就要回退了，所以我们继续再判断是否
e
x
[
i
−
1
]
−
1
>
e
x
[
3
]
ex[i-1]-1 > ex[3]
ex[i−1]−1>ex[3]（决定
e
x
[
i
+
1
]
ex[i+1]
ex[i+1] ） …… 最后起码会止步于
e
x
[
i
−
1
]
−
1
>
e
x
[
i
−
1
]
ex[i-1]-1>ex[i-1]
ex[i−1]−1>ex[i−1] 的判断（因为这肯定不成立），因此不存在访问了未计算部分的情况。
要是对于决定
e
x
[
i
+
x
−
2
]
ex[i+x-2]
ex[i+x−2] 的判断，
e
x
[
i
−
1
]
−
1
≤
e
x
[
x
]
ex[i-1]-1 ≤ ex[x]
ex[i−1]−1≤ex[x] 呢？那就暴力从
i
+
e
x
[
i
−
1
]
−
2
i+ex[i-1]-2
i+ex[i−1]−2 再向右扩展就是了。这样一来就不会向左回退，只会向右扩展，保证了复杂度线性。
模板
void INITex(char *ss,int *ex,int n) {
ex[0] = 0;ex[1] = n;ex[2] = 0;
int l = 0,r = 0;
for(int i = 2;i <= n;i ++) { ex[i] = 0;
if(i <= r) ex[i] = min(ex[i-l+1],r-i+1);
while(i + ex[i] <= n && ss[i+ex[i]] == ss[ex[i]+1]) ex[i] ++;
if(i + ex[i] - 1 > r) l = i,r = i + ex[i] - 1;
}
return ;
}Subtask 2 ···
也可以仿照
e
x
[
]
ex[]
ex[] 的计算。
不妨设
G
[
i
]
G[i]
G[i] 为
S
1
S1
S1 的第
i
i
i 位的后缀与
S
2
S2
S2 的最长公共前缀。
类似地，首先，
G
[
1
]
G[1]
G[1] 可以暴力跑出来。 1
然后，遍历到每一个
i
i
i ，若
G
[
i
−
1
]
−
1
>
e
x
[
2
]
G[i-1]-1 > ex[2]
G[i−1]−1>ex[2] （注意这里是
e
x
[
2
]
ex[2]
ex[2]），则
G
[
i
]
=
e
x
[
2
]
G[i]=ex[2]
G[i]=ex[2]，然后继续判是否
G
[
i
−
1
]
−
1
>
e
x
[
3
]
G[i-1]-1>ex[3]
G[i−1]−1>ex[3] 来决定 G[i+1] …… 这里就不用担心未计算的问题，因为
e
x
[
]
ex[]
ex[] 肯定都处理完了。
直到找到一个不成立的，就从
i
+
G
[
i
−
1
]
−
2
i+G[i-1]-2
i+G[i−1]−2 再向右找，和
S
u
b
t
a
s
k
1
Subtask\;1
Subtask1 类似。
模板
for(int i = 1;i <= n;i ++) {if(s2[i] == s1[i]) G[1] = i;else break;}
int l = 1,r = G[1];
for(int i = 2;i <= n;i ++) { G[i] = 0;
if(i <= r) G[i] = min(ex[i - l + 1],r - i + 1);
while(i + G[i] <= n && s1[i + G[i]] == s2[G[i] + 1]) G[i] ++;
if(i + G[i] - 1 > r) l = i,r = i + G[i] - 1;
}特
此
说
明
一
下
，
本
文
中
的
字
符
串
下
标
从
1
开
始
，
也
就
是
说
下
标
0
表
示
空
串
_{特此说明一下，本文中的字符串下标从1开始，也就是说下标 0 表示空串}
特此说明一下，本文中的字符串下标从1开始，也就是说下标0表示空串 ︎ ︎ ︎ ︎
