引
入
引入
引入
“ 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表示空串 ︎ ︎ ︎ ︎