0%

KMP字符串模式匹配算法的两种实现

暴力马拉车(BF)的时代结束了,来看看KMP算法吧,简单易用方便快捷!

直接上码

废话不多说,直接上代码

1.动态规划|有限状态自动机

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
class KMP {
private:
string pat;
int **dp;

public:
KMP(string _pat) {
pat = _pat;
dp = new int *[pat.length()];
dp[0] = new int[256];
dp[0][pat[0]] = 1;
for (int x = 0,j = 1; j < pat.length(); j++) {
dp[j] = new int[256];
for (int i = 0; i < 256; i++)
dp[j][i] = i == pat[j] ? j + 1 : dp[x][i];
x = dp[x][pat[j]];
}
}
int find(string text) {
int j = 0;
for (int i = 0; i < text.length(); i++) {
j = dp[j][text[i]];
if (j == pat.length())
return i - j + 1;
}
return -1;
}
~KMP() {
int x = pat.length();
while (x--)
delete[] dp[x];
delete[] dp;
}
};

2.动态规划|空间最优

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
class KMP {
private:
string pat;
int *next;

public:
KMP(string _pat) {
pat = _pat;
next = new int[pat.length()];
next[0] = 0;
for (int i = 1, j = 0; i < pat.length(); i++) {
while (j > 0 && pat[i] != pat[j])
j = next[j - 1];
next[i] = pat[i] == pat[j] ? ++j : j;
}
}
int find(string text) {
for (int i = 0, j = 0; i < text.length(); i++) {
while (j > 0 && text[i] != pat[j])
j = next[j - 1];
if (text[i] == pat[j])
j++;
if (j == pat.length())
return i - j + 1;
}
return -1;
}
~KMP() { delete[] next; }
};

优劣

两段代码都非常的容易理解:

代码1是正向思考,枚举在字符串匹配中可能遇到的所有情况,将这些情况的状态变化记录成DP数组,在查找的时候直接无脑代入DP数组就好了,代码看起来繁复的部分基本是由于开二维数组造成的。

代码2是递推思考,思考如果在匹配pattern[n]的时候如果匹配不上就往前推进到前一个前缀字符串相同的位置,直到匹配成功或者彻底失败,然后重新匹配。

很明显,代码1是空间换时间的做法,如果需要匹配的对象有明确的范围的话(例如为ASCII范围内)且需要匹配的pattern串长度合适或者需要多次使用,代码1明显更合适。

而代码2中规中矩,基本是KMP最基本的思路,相对可用范围也更宽泛一些,但是在面对重复多次的恶意数据仍然有超时风险。

结论就是:DP党无脑冲1,CPC日常写2(2的码量更小)

讲解

想要看懂KMP,最关键的是要能明白KMP为什么能这么干,也就是KMP的理论依据:

如果text[a:b]匹配pattern[c:d]

那么显然对于pattern[c:d]中的任何pattern[x:d]都有text[y:b]与之对应

如果存在pattern[c:z]与pattern[x:d]相同

那么显然text[y:b]与pattern[c:z]匹配

推理过程如上,稍作理解一下即可,简单来说就是如果已知两段字符串匹配,那么更短相同前缀的模式字符串显然也在同一个位置完全匹配。

如果pattern[j]与当前的text[i]并不匹配,那我们就可以尝试去查询pattern中出现的更短相同前缀的位置,来寻找是否有可以匹配的字符,这样就可以规避大量无意义的繁复“马拉车”。

这也是KMP算法的精髓所在——头可断血可流,字符串绝对不回推。

为了更好的装逼解释这个过程,我们引入动态规划状态的概念,对于一个长度为$N$的pattern串,认为这个串并不是线性的,而是有$N$个状态分立,处理每个状态时在不同的情况下可能转向不同的状态。

显然当pattern转为第$N+1$个状态时,发生了完整的匹配。

既然如此,状态在不同情况下的转移条件就成为了关键,那么状态转移的条件是什么呢?

代码1和代码2选择了不同的方法描述这个条件:

代码1

代码1选择开辟了一个二维数组

1
int dp[pat.length()][256];

这个数组的功能也很明显,对于每个状态dp[i]记录当这个状态遇见字符’c’时的转移路径dp[i][c]

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//必要时需要对dp数组进行初始化
//初始化:当且仅当状态0遇到pat[0]时发生转移到状态1
dp[0][pat[0]] = 1;
//开辟一个变量作为影子状态指针,影子状态存在的原因解释在下文
int x = 0;
//遍历pattern字符串,从1开始
for (int j = 1; j < pat.length(); j++) {
//遍历ASCII全集情况下的状态转移方式
for (int i = 0; i < 256; i++)
//显然当i==pat[j]时转移到顺序下一状态即j+1
//当i!=pat[j]时,dp[j][i]取决于影子位置遇到i时的转移方式
dp[j][i] = i == pat[j] ? j + 1 : dp[x][i];
//跟进影子状态,将遇到当前字符时影子状态的转移赋给影子状态即影子状态跟进一位
x = dp[x][pat[j]];
}

理解这个代码的核心在于理解影子状态的存在。

每个状态i,在遇到pat[i]的时候转移到顺序状态很好理解,但是其他的情况如何转移呢?

最朴素的思路就是从x=[0:i]依次查找[x:i]是否存在一个最长的字符串与pattern串从0开始完全匹配——等等,匹配?!我们不是正在写用于匹配计算的状态转移数组嘛!

我们是从位置1开始遍历,刚刚好位置0的转移已经写好了,那么如果我们在推进遍历的过程中持续将当前pat[i]输入状态转移数组,维护一个从位置0开始匹配的X,那么显然X的位置就是最长的更短相同前缀字符串的位置。任意位置i在遇到任何c!=pat[i]的时候的处理方式,可以完全参照i状态的影子状态X的处理方式——既然i状态遇到C无法更进一步到顺序下一个位置,那么就尽可能的前往pattern串中更偏后的位置。

转移数组会在推进的过程中越来越复杂,显然的对于几个具有相同短前缀的位置,后一个位置会通过X继承前一个位置的全部转移方式。

使用这种方法生成dp数组后,在进行查找的时候只需要无脑放心的顺序将text串的每一个字符塞进转移数组就好了,每次判断一下是否抵达完全匹配的状态即可。

代码2

代码2记录转移路径的方法是开辟了一个一维数组

1
int next[pat.length()];

核心代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//next[i]中记录的是状态i+1最近的相同前缀的状态的位置
//如果不能理解第一行这句话可以先看下文
//如此如果状态0匹配失败下一次仍然匹配状态0,同时也应该注意到需要对状态0进行特判
next[0] = 0;
//开辟一个变量记录影子状态j
int j = 0;
//遍历pattern字符串
for (int i = 1; i < pat.length(); i++) {
//如果影子状态j与当前状态i字符不相同,则j转移到上一个有相同前缀的位置进行尝试
//显然这种特殊的记录方式数学本质使然,加之状态0的特殊情况,显然不能查找状态0的上一状态
//所以需要在这里对j=0进行特判,此处j>0替换为j!=0不会发生任何错误
while (j > 0 && pat[i] != pat[j])
//如果pat[j]匹配失败,显然pat[0:j-1]已经完全匹配成功,那么显然pat[0:next[j-1]]已经匹配
//因此可以通过j = next[j - 1]转移到相同前缀字符串待匹配的位置
j = next[j - 1];
//退出while循环有两种可能,如果是因为pat[i] == pat[j]退出,
//那么显然pat[0:j]与pat[x:i]完全匹配-》j+1状态是i+1状态最近的相同前缀状态
//按照next[]记录规则将++j赋给next[],同时维护了影子状态
//如果是因为j=0退出那么显然在i状态之前已经没有更短相同前缀状态,此时给next[i]赋j皆可
next[i] = pat[i] == pat[j] ? ++j : j;
}

临时兴起改的减缩版

1
2
for(int i=1,j=next[0]=0;i<pat.length();next[i++]=pat[i]==pat[j]?++j:j)
while(j>0&&pat[i]!=pat[j])j=next[j-1];

因为对于任何一个状态i只需要考虑前一个更短相同前缀的状态在哪里,原理倒是很好理解,递归查找嘛。

这段代码不好理解的地方主要就是因为太精炼,next数组的意义太绕了。

next[i-1]记录的是如果状态i匹配失败下一步需要匹配的状态!如果能理解这一点那么这段代码就能完全理解了!

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道