写点什么

KMP 的小记录

用户头像
Geek_02fd98
关注
发布于: 2021 年 03 月 03 日

之前每次在做题的时候,都没法很好的理解 KMP 算法的思路,每次都是写的磕磕绊绊的,导致没法很好的利用 KMP 来完成相应的习题。这次想借这个机会总结一下 KMP。希望对自己有帮助,如果能对看文章的您有一丝丝帮助,万分荣幸。

KMP 算法:就是三个外国大佬设计的方法,取了每个人名字的一个字母,组成了这个名字。算法时间复杂度为 O(两个字符串长度和)主要是用在了字符串的模式匹配上面。核心主要是利用匹配失败的信息来完成下一次匹配。在 Leetcode 上面的标准习题就是各种字符串之间的互相匹配,这种习题,一般暴力法是肯定可以解决的,但是还有 KMP 的算法值得一试。

算法大致思路:m=aaaccaaad n=aaad,要在 m 中找到 n 的匹配信息

1、 首先从左开始匹配 m,n 发现到了第一个 c 处开始无法匹配

2、 这时候比较基础的就是,从下一个字符开始继续比较,这种就是暴力解法。

3、 所以就需要根据之前的正确匹配的结果去滑动,就可以避免多次暴力求解过程中的多次重复求解。

上面的逻辑一般在很多地方都可以看到,一般询问最多的是 next 数组是怎么求解出来的。其实就是首位重合的字符的个数。next[j+1]=next[j]+1;比如 abaabcabc 的情况,

位序       1   2   3   4   5   6   7   8   9   

模式串     a   b   a   a   b   c   a   b   c   

next 值     0   1   1   2   2   3   1   2   3   

int GetNext(char ch[],int next[]){    int len = ch.length;    next[1] = 0;    int i = 1,j = 0;    while(i< len){        if(j==0||ch[i]==ch[j]) next[++i] = ++j;        else j = next[j];    }}
复制代码


1.第一位的 next 值为 0

2.第二位的 next 值为 1

后面求解每一位的 next 值时,根据前一位进行比较

3.第三位的 next 值:第二位的模式串为 b ,对应的 next 值为 1;将第二位的模式串 b 与第一位的模式串 a 进行比较,不相等;则第三位的 next 值为 1(其他情况均为 1)

4.第四位的 next 值:第三位的模式串为 a ,对应的 next 值为 1;将第三位的模式串 a 与第一位的模式串 a 进行比较,相同,则第四位的 next 值得为 1+1=2;以此类推。

对应习题:

459: https://leetcode-cn.com/problems/repeated-substring-pattern/

28: https://leetcode-cn.com/problems/implement-strstr/

686:https://leetcode-cn.com/problems/implement-strstr/

 

用户头像

Geek_02fd98

关注

还未添加个人签名 2020.07.31 加入

还未添加个人简介

评论

发布
暂无评论
KMP的小记录