字符串模式匹配（3）————KMP算法（2）—求next数组

作者： 作者的头像   Meng123456 ,  2022-04-15 10:14:37 ,  所有人可见 ,  阅读 401

1


1

0.png

串这一章在408考试大纲中隶属于查找部分
9·1.png

而且近几年涉及的串的内容都是KMP算法，根据王道老师分析408考试中KMP算法求next数组只会考手算方法，因此这里只介绍KMP算法传统的手算求next数组。

KMP算法

1.png

手算求next数组

在上一节我们介绍了KMP算法以及next数组的使用方法，而这一节我们讨论next数组的求法
第一趟
1·1.png

1·2.png

1·3.png

任何next数组的next【1】都是0。
第二趟
2·1.png

2·2.png

任何next数组的next【2】都是1。
第三趟
3·1.png

3·2.png

3·3.png

第四趟
4·1.png

4·2.png

4·3.png

4·4.png

4·5.png

4·6.png

第五趟
5·1.png

5·2.png

5·3.png

5·4.png

5·5.png

5·6.png

第六趟
6·1.png

6·2.png

6·3.png

6·4.png

6·5.png

6·6.png

6·7.png

总结

next[1]都⽆脑写0

next[2]都⽆脑写1

其他next：在不匹配的位置前，划⼀根美丽的分界线模式串⼀步⼀步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为⽌。此时j指向哪⼉，next数组值就是多少

7·1.png

7·2.png

8·1.png

0 评论