字符串匹配: KMP算法
学习于 从头到尾彻底理解KMP
结合自己的理解, 本文致力于从简介绍
先给出模板代码
void KMP(char *s, char *t, int *p);
在文本串 s 中寻找模板串 t 的匹配, 需要长度至少为strlen(t)+1的辅助空间
串 s 和 t 的下标都是从0开始 (从1开始见后)
void KMP(char *s, char *t, int *f)
{
int lens = strlen(s), lent = strlen(t);
f[1] = 0;
for(int i = 1, j = 0; i < lent; f[++i]=j) {
while(j && t[j] != t[i]) j = f[j];
if(t[i] == t[j]) j++;
}
for(int i = 0, j = 0; i < lens; i++) {
while(j && s[i] != t[j]) j = f[j];
if(s[i] == t[j]) j++;
if(j == lent) { /*匹配成功*/ j = f[j];}
}
}
问题原型: 字符串匹配
给定文本串 s 和模板串 t
在 s 中查找 t 出现了多少次或者出现的位置
比如在文章中查找一个单词
暴力方案
最容易想到的就是暴力匹配, 从 s 串的每一个位置开始匹配 t 串
void str_match(char *s, char *t)
{
int lens = strlen(s), lent = strlen(t);
for(int i = 0; i < lens; i++)
for(int j = 0; j < lent && i+j < lens; j++) {
if(s[i+j] != t[j]) break;
if(j+1 == lent) /*匹配成功*/;
}
}
暴力匹配的时间复杂度是 O(lens*lent)
以 表示 s 串上的匹配位置,
表示 t 串上的匹配位置
发现, 当前位置匹配成功时, ++,
++
而匹配失败时, 回到0, 同时
也会"回溯", 退回到 i+1, 重新开始匹配
因此时间复杂度为O(lens*lent)
而KMP算法, 则利用已经匹配的信息, 实现了 不回溯, 优化了性能
KMP算法
在暴力方法中, 对于两个串:
0 1 2 3 4 5 6 7 8 9
a b a b c a b a b d
a b a b d
匹配到 时匹配失败, 然后
,
相当于将串 t 右移一位然后从头开始匹配
0 1 2 3 4 5 6 7 8 9
a b a b c a b a b d
_ a b a b d
然而实际上我们知道这时必然会匹配失败
流程模拟
KMP算法的做法是直接移动到:
0 1 2 3 4 5 6 7 8 9
a b a b c a b a b d
_ _ a b a b d
并且 不改变,
, 继续和
匹配, 再次失败, 则:
0 1 2 3 4 5 6 7 8 9
a b a b c a b a b d
_ _ _ _ a b a b d
, 而如果这时再次失败, 则
++
原理理解
当第一次匹配失败时, 完全不需要将 t 只右移一位, 这由 t 自身决定:
a b a b d 如果在t[4]匹配失败, 说明与之匹配的s的前四位已知, 是 a b a b
右移一位会使b与a匹配, 所以必定会失败
而右移两位同样是由 t 自身决定:
a b a b d 如果在t[4]匹配失败, 说明与之匹配的s的前四位已知, 是 a b a b
串 s 在 之前的这个长度为4的子串的后缀与
串 t 在 之前的这个长度为4的子串的前缀
有长度为2的相同部分a b
所以这时, 无需重新匹配已经匹配过的部分, 可以直接右移两位
核心便在于, 已经匹配成功的子串的相同的前缀和后缀的长度 f
所以这个辅助空间f数组, f[i]表示串 t [0, i-1]子串的相同前缀后缀长度
知道了这个长度, 就是匹配失败时右移的长度, 就可以直接"跳跃式"移动
可以写出伪代码:
KMP(s, t, f)
{
for(i = 0, j = 0; i < lens; i++)
{
while(j && s[i] != t[j]) j = f[j];
if(s[i] == t[j]) j++;
if(j == lent) {/*匹配成功*/ j = f[j];}
}
}
每一次for循环结束 ++, 或是
与
匹配成功, 或是
与
匹配失败
- 第一个while是不断失配时, 串 t 沿着 f 数组右移, 直到
- 之后判断能否匹配, 如果能匹配, 则应有
++,
++
- 如果不能匹配, 则此时
- 如果
再举个例子
s: a b c a b c d e f g a b c a b c a b c a b c a b c
t: a b c a b c a b
f: 0 0 0 0 1 2 3 4 5
在 ,
时匹配失败
已经成功匹配的长度为6的子串a b c a b c的 f 值为3
便有 , 此时
不变, 相当于串 t 右移三位(6-3=3):
a b c a b c d e f g a b c a b c a b c a b c a b c
_ _ _ a b c a b c a b
这时再次失配, 而这时成功匹配的长度为3的子串a b c的 f 值为0
便有 , 此时
不变, 相当于串 t 右移三位(3-0=3):
a b c a b c d e f g a b c a b c a b c a b c a b c
_ _ _ _ _ _ a b c a b c a b
当 时匹配失败, 则
++, 直到
a b c a b c d e f g a b c a b c a b c a b c a b c
_ _ _ _ _ _ _ _ _ _ a b c a b c a b
(与
匹配成功则同时加一)
这时在 ,
第一次匹配成功
但是对串 s 的匹配还没有结束, 这时仍然沿着 f 移动
相当于在 处匹配失败, 已经匹配成功的为 t, 而 t 相同的前缀和后缀长度为5
所以有 , 相当于右移三位(8-5=3):
a b c a b c d e f g a b c a b c a b c a b c a b c
_ _ _ _ _ _ _ _ _ _ _ _ _ a b c a b c a b
这时会从 ,
匹配到
再次成功
...... ......
算法实现
预处理
首先应该对于串 t 预处理出来 f 数组
f[i]表示串 t [0, i-1]子串的最长相同前缀后缀的长度, 所以它有效的范围是[1, strlen(t)]
并且注意前缀后缀不能是自身, 故 f[i] <= i-2
f[0]没有意义, 设为0即可, 初始化f[1] = 0
之后求出 f 数组的过程, 相当于串 t 自己与自己匹配:
尝试用已经求出 f 值的部分来匹配正在求的 f 值
你有可能会想到递推, 对于 f[i], 可以根据 f[i-1] 和 t[i-1] == t[f[i-1]] 来得出
反例: a a b a a a
因此代码写起来和匹配串 s 很像, 伪代码:
KMP_pre(t, f)
{
f[1] = 0;
for(i=1, j=0; i < lent; i++)
{
while(j && t[i] != t[j]) j = f[j];
if(t[i] == t[j]) j++;
f[i+1] = j;
}
}
伪代码里, 第 i 次循环求的是 [0, i] 的最长相同前缀后缀, 所以赋值给 f[i+1]
这里, i 就相当于 , j 便是
a b c a b c a b
当有 f[1] = 0 时, 这时我们在求 f[2], 表示 a b 的最长相同前缀后缀长度
,
, 相当于这样的比较:
a b c a b c a b
_ a
"自己与自己匹配", 显然这一次会匹配失败, 因此 f[2] = 0, 也就不会增加
a b c a b c a b
_ _ a b
不变,
++, 相当于模板串右移一位, 只不过这一次模板串会逐增而已
a b c a b c a b
_ _ _ a b c
匹配
看过前面的原理理解, 应该已经明白了
并且想要顺利看懂算法实现-预处理, 也要求应该先明白匹配过程
或许, 这是这篇文章思路不合理的地方吧
模板代码
void KMP(char *s, char *t, int *f)
{
int lens = strlen(s), lent = strlen(t);
f[1] = 0;
for(int i = 1, j = 0; i < lent; f[++i]=j) {
while(j && t[j] != t[i]) j = f[j];
if(t[i] == t[j]) j++;
}
for(int i = 0, j = 0; i < lens; i++) {
while(j && s[i] != t[j]) j = f[j];
if(s[i] == t[j]) j++;
if(j == lent) { /*匹配成功*/ j = f[j];}
}
}
如果你习惯从 1 开始字符串下标的话, 明白算法原理之后, 就很容易改得出来这些细节了:
void KMP(char *s, char *t, int *f)
{
int lens = strlen(s+1), lent = strlen(t+1);
f[1] = 1;
for(int i = 2, j = 1; i <= lent; f[++i]=j) {
while(j > 1 && t[j] != t[i]) j = f[j];
if(t[i] == t[j]) j++;
}
for(int i = 1, j = 1; i <= lens; i++) {
while(j > 1 && s[i] != t[j]) j = f[j];
if(s[i] == t[j]) j++;
if(j > lent) { /*匹配成功*/ j = f[j];}
}
}
