写点什么

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

  • 2022 年 5 月 15 日
  • 本文字数:2404 字

    阅读完需:约 8 分钟

二、长度为前 2 个字符的子串aa,最长相同前后缀的长度为 1。



三、长度为前 3 个字符的子串aab,最长相同前后缀的长度为 0。



以此类推:


四、长度为前 4 个字符的子串aaba,最长相同前后缀的长度为 1。


五、长度为前 5 个字符的子串aabaa,最长相同前后缀的长度为 2。


六、长度为前 6 个字符的子串aabaaf,最长相同前后缀的长度为 0。


那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图:



可以看出前缀表里的数值代表着就是:当前位置之前的子串有多大长度相同的前缀后缀


再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示:



找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。


为什么要看前一个字符的前缀表的数值呢,因为要找前面字符串的最长相同的前缀和后缀。


所以要看前一位的 前缀表的数值。


前一个字符的前缀表的数值是 2, 所有把下表移动到下表 2 的位置继续比配。可以再反复看一下上面的动画。


最后就在文本串中找到了和模式串匹配的子串了。


[](()前缀表有什么问题




来看一下刚刚求的这个前缀表有什么问题呢?


![](https://img-blog.csdnimg.cn/img_convert/5a1166763cad897 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 8e44806d7f71021e9.png)


看这个位置红框的位置,如果要找下表 1 所对应 前缀表里的数值的时候,前缀表里的数值依然是 1,然后就要跳到下表 1 的位置,如此就形成了一个死循环


**如何怎么避免呢,就把前缀表里的数值统一减一, 开始位置设置为-1 **。 这一点对理解后面 KMP 代码很重要!!


改为如图所示:



这样就避免的死循环,只不过后续取 前缀表里的数值的时候,要记得再+1,才是我们想要的值。


最后得到的新前缀表在 KMP 算法里通常用一个 next 数组来表示。


注意这个 next 数组就根据模式串求取的。


[](()使用 next 数组来匹配




有了 next 数组,就可以根据 next 数组来 匹配文本串 s,和模式串 t 了。


注意 next 数组是新前缀表(旧前缀表统一减一了)。


匹配过程动画如下:



[](()放码过来




下文统称 haystack 为文本串, needle 为模式串。


[haystack, needle 出处](()。

[](()构造 next 数组

定义一个方法 getNext 来构建 next 数组,参数为一个名为 next 数组,和一个字符串。代码如下:


private void getNext(int[] next, String s) {}


构造 next 数组其实就是计算模式串 s,前缀表的过程。主要有如下三步:


  1. 初始化

  2. 处理前后缀不相同的情况

  3. 处理前后缀相同的情况

[](()一、初始化

定义两个指针 i 和 j:


  • j 指向前缀终止位置(严格来说是终止位置减一的位置),

  • i 指向后缀终止位置(与 j 同理)。


(通常是先 i 后 j,为什么这里相反,接下来看代码就清楚了。)


然后还要对 next 数组进行初始化赋值,如下:


int j = -1;


next[0] = j;


  • j 初始化为 -1 原因是前文说过前缀表要统一减一的操作(避免死循环得情况),所以 j 初始化为-1。

  • next[] 表示 i(包括 i)之前最长相等的前后缀长度(其实就是 j),next[0]初始化为 j 。

[](()二、处理前后缀不相同的情况

因为 j 初始化为-1,那么 i 就从 1 开始,进行 s[i] 与 s[j+1]的比较。(这里可能一开始不适应理解,不用急。)


所以遍历模式串 s 的循环下表 i 要从 1 开始,代码如下:


for(int i = 1; i < s.length(); i++) { // 注意 i 从 1 开始


如果 s[i] 与 s[j+1]不相同,也就是遇到 前后缀末尾不相同的情况,就要回退。


如何回退?next[j]就是记录着 j(包括 j)之前的子串的相同前后缀的长度。


那么 s[i] 与 s[j+1] 不相同,就要找 j+1 前一个元素在 next 数组里的值(就是 next[j])。


所以,处理前后缀不相同的情况代码如下:


while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 前后缀不相同了


j = next[j]; // 回退


}

[](()三、处理前后缀相同的情况

如果 s[i] 与 s[j + 1] 相同,那么就同时向后移动 i 和 j 说明找到了相同的前后缀,同时还要将 j(前缀的长度)赋给 next[i], 因为 next[i]要记录相同前后缀的长度。


代码如下:


if (s.charAt(i) == s.charAt(j + 1)) { // 找到相同的前后缀


j++;


}


next[i] = j; // 将 j(前缀的长度)赋给 next[i]


最后整体构建 next 数组的函数代码如下:


private void getNext(int[] next, String s) {


int j = -1;


next[0] = j;


for(int i = 1; i < s.length(); i++) { // 注意 i 从 1 开始


while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 前后缀不相同了


j = next[j]; // 向前回溯


}


if (s.charAt(i) == s.charAt(j + 1)) { // 找到相同的前后缀


j++;


}


next[i] = j; // 将 j(前缀的长度)赋给 next[i]


}


}


代码构造 next 数组的逻辑流程动画如下:



得到了 next 数组之后,就开始用它做匹配。

[](()使用 next 数组来做匹配

在文本串 haystack 里找是否出现过模式串 needle。定义两个下表 j 指向模式串起始位置,i 指向文本串其实位置。


那么 j 初始值依然为-1,这是因为 next 数组里记录的起始位置为-1


i 就从 0 开始,遍历文本串,代码如下:


for (int i = 0; i < haystack.length(); i++) { // 注意 i 就从 0 开始


接下来就是 haystack.charAt(i) 与 needle.charAt(j + 1) (因为 j 从-1 开始的) 进行比较。


如果 haystack.charAt(i) 与 needle.charAt(j + 1) 不相同,j 就要从 next 数组里寻找下一个匹配的位置。


代码如下:


while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { // 不匹配


j = next[j]; // j 寻找之前匹配的位置


}


如果 haystack.charAt(i) 与 needle.charAt(j + 1) 相同,那么 i 和 j 同时向后移动, 代码如下:


if (haystack.charAt(i) == needle.charAt(j + 1)) { // 匹配,j 和 i 同时向后移动


j++;


}


如果 j 指向了模式串 t 的末尾,那么就说明模式串 t 完全匹配文本串 s 里的某个子串了。


本题要在文本串字符串中找出模式串出现的第一个位置(从 0 开始),所以返回当前在文本串匹配模式串的位置 i 减去 模式串的长度,就是文本串字符串中出现模式串的第一个位置。


代码如下:


if (j == (needle.length() - 1) ) { // 文本串 s 里出现了模式串 t


return (i - needle.length() + 1);


}

[](()代码总览

用户头像

还未添加个人签名 2022.04.13 加入

还未添加个人简介

评论

发布
暂无评论
KMP子字符串匹配算法学习笔记_Java_爱好编程进阶_InfoQ写作社区