学习笔记 - KMP字符串匹配算法

其实之前学过好多次了,都没有学懂……
现在学懂了(写一篇博客免得忘掉)


Part1. 字符串匹配问题

在这个问题中,给出两个字符串 $S,T$,要求回答 $T$ 是否是 $S$ 的一个子串。

关于 $S,T$,在字符串匹配问题中,$S$ 称为主串,$T$ 称为模式串。那么我们就是要在主串中找模式串。


Part2. Brute-Force

顾名思义,暴力算法。设主串 $S$ 长度为 $n$,模式串 $T$ 长度为 $m$。那么我们暴力地枚举每个 $S$ 的子串(其实就是枚举每个子串的开始位置),复杂度 $O(n)$;然后对于每个子串,暴力检测子串是否与 $T$ 相同,复杂度 $O(m)$。

所以复杂度为 $O(nm)$。显然太慢了,尤其是主串 $n$ 比较大的时候。


Part3. KMP 算法

“KMP” 是算法提出者(不止一个人,但是我忘了 awa)的名字缩写。

Part3/1. 算法思路

首先分析 Brute-Force 的缺陷:完全没有利用上一次匹配得到的信息,每一次匹配要将模式串的指针和主串的指针都回溯到起始位置。

相反,KMP 就尽可能地利用了已有的匹配信息,并且不再回溯主串的指针,而是把 模式串向右移动。而且模式串向右移动并不是简单的右移一位,而是移动到尽可能远的、可能匹配的位置。

下面这种情况,$S_{i-j+1\to i-1}$ 和 $T_{0\to j-1}$ 已经匹配,但是在 $S_i,T_j$ 这个位置失配,就像下图这样:
jpg2

那么我们考虑把 T 向右移动,假设移动到 $S_i$ 对应 $T_k$ 时,$S_{i-k\to i-1}$ 和 $T_{0\to k}$ 匹配了。
jpg2

(并不知道 $S_i$ 和 $T_k$ 是否会匹配)说明 $k$ 是下一个可能匹配的位置。于是我们把 $T$ 的指针移动到 $k$ 继续匹配。

在 KMP 中,当 k 和 j 满足上述关系时,定义 fail 指针 $fail(j)=k$。

Part3/2. fail 指针的性质

考虑 $k$ 和 $j$ 满足什么条件,$fail(j)=k$。

jpg3

框起来的这部分一定完全一样,不然 $T_{0\to k-1}$ 不可能和 $S_{i-k\to i-1}$ 匹配。也就是 $T_{0\to k-1}=T_{j-k\to j-1}$,所以 fail 指针其实和主串 $S$ 没有关系,只跟 $T$ 本身相关。

根据定义,以及算法的特殊设计:

如果 $i=0$,即模式串的开头就失配了,就只有把模式串向右移一位了,于是 $fail(0)=-1$。如果存在这样的 $k$,就可以将模式串向右移动到尽可能远的位置(所以是取 $\max$)。如果不存在这样的 $k$,就只有把模式串挪到开头,尝试匹配。

Part3/3. KMP 主函数

有了 fail 指针,我们就可以不再回溯主串的指针,而是将模式串向右挪到 $fail()$ 的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int KMP(){
int cnt=0;
int i=0,j=0; //i是主串的指针,j是模式串的指针
while(i<lenS){
if(j==-1 || S[i]==T[j])
//两种情况:①两位置匹配;②j=-1即需要将模式串右移一位
i++,j++;
else
//跳转 fail 指针
j=fail[j];
if(j==lenT) //T匹配完了,说明已经找到匹配的子串
cnt++,
j=fail[j]; //继续找下一个子串
}
return cnt;
}

Part3/4. 求 fail 指针

最难计算的显然是 $fail(j)=\max\{k|T_{0\to k-1}=T_{j-k\to j-1}\}$ 的情况嘛。

假如我们已经计算出来了 $fail(j)$,怎样递推的求出 $fail(j+1)$?

  1. 如果 $T_{fail(j)}=T_{j}$,那么就可以向后匹配一位,也就是 $fail(j+1)=fail(j)+1$;
  2. 否则就相当于把 $T$ 同时作为模式串、主串进行匹配,在 $T_{fail(j)}$ 和 $T_j$ 位置失配,照样采用 KMP 的思想,将 j 跳回 $fail(j)$ 的位置,继续匹配,直到匹配成功或者退回到起始位置;
1
2
3
4
5
6
7
8
void GainFail(){
fail[0]=-1;fail[1]=0; //fail(1)=0 是可以从定义式中推出来的
int i=1,j=0; //把 T 同时作为主串、模式串,i,j 分别为主串、模式串的指针
while(i<lenT){
if(j==-1 || T[i]==T[j]) fail[++i]=++j;
else j=fail[j];
}
}

Part4. 不如来手玩一下?

标号: 0 1 2 3 4 5 6 7
模式串:b c a b c a a b

计算过程:

  1. $fail(0)=-1,fail(1)=0$;此时两个指针 $i=1,j=0$
  2. $T_i\not=T_j$,$j$ 退回到 $fail(j)=0$,仍未匹配,退回到 $fail(j)=-1$;回到起始位置 $fail(i+1)=j+1=0$;此时 $i=2,j=0$
  3. $T_i\not=T_j$,$j$ 退回到 $fail(j)=-1$,回到起始位置 $fail(i+1)=j+1=0$;此时 $i=3,j=0$
  4. $T_i=T_j$,匹配,$fail(i+1)=j+1=1$;此时 $i=4,j=1$
  5. $T_i=T_j$,匹配,$fail(i+1)=j+1=2$;此时 $i=5,j=2$
  6. $T_i=T_j$,匹配,$fail(i+1)=j+1=3$;此时 $i=6,j=3$
  7. $T_i\not=T_j$,$j$ 退回到 $fail(j)=0$ 仍未匹配,$j$ 退回到 $fail(j)=-1$;回到起始位置,$fail(i+1)=0$;此时 $i=7,j=0$
  8. $T_i=T_j$,匹配,$fail(i+1)=j+1=1$

结果是

fail:-1 0 0 0 1 2 3 0 1


Part5. 源代码

> 模板题 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000000;

char S[N+3],T[N+3];
int fai[N+3];
int lenS,lenT;

void GainFail(){
fai[0]=-1;fai[1]=0;
int i=1,j=0;
while(i<lenT){
if(j==-1 || T[i]==T[j]) fai[++i]=++j;
else j=fai[j];
}
}
void KMP(){
int i=0,j=0;
while(i<lenS){
if(j==-1 || S[i]==T[j]) i++,j++;
else j=fai[j];
if(j==lenT) printf("%d\n",i-lenT+1),j=fai[j];
}
}
int main(){
scanf("%s%s",S,T);
lenS=strlen(S),lenT=strlen(T);
GainFail();
KMP();
for(int i=1;i<=lenT;i++){
if(i>1) printf(" ");
printf("%d",fai[i]);
}
printf("\n");
return 0;
}

The End

Thanks for reading!

字符串好快乐啊~ (打脸)

0%