数据结构与算法简记--字符串匹配KMP算法

蜗牛慢爬的李成广 2020-01-11

KMP算法


比较难理解,准备有时间专门啃一下。 

核心思想与BM算法一样:假设主串是 a,模式串是 b。在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,我们希望找到一些规律,可以将模式串往后多滑动几位,跳过那些肯定不会匹配的情况。

不同的是:在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫作坏字符,把已经匹配的那段字符串叫作好前缀

关键找相等的最长匹配前缀和最长匹配后缀。
有两种情况,
(1)如果b[i-1]的最长前缀下一个字符与b[i]相等,则next[i]=next[i-1]+1.
(2)如果不相等,则我们假设找到b[i-1]的最长前缀里有b[0,y]与后缀的子串b[z,i-1]相等,然后只要b[y+1]与b[i]相等,那么b[0,y+1]就是最长匹配前缀。这个y可以不断的通过迭代缩小就可以找到

https://www.zhihu.com/question/21923021,逍遥行 的回答

 

相关推荐

henryzhihua / 0评论 2020-06-17