我对KMP算法的一点总结

我对KMP算法的一点总结

1.

KMP字符串匹配算法中重要的部分是获得next数组,然后通过next数组寻找当文本串和模式串不匹配时模式串的字符回退的位置。并且在文本串和模式串不匹配时,文本串不需要回退,接着当前的文本串的字符继续匹配。

2.

为什么要用next数组做回退呢,因为next数组记录的是最长相等前后缀的长度,这个长度减 1 就是最长相等前后缀的前缀的最后一个字符在模式串的位置。
当匹配到不相等的字符,该字符前面的字符都是已经匹配的字符,可以通过该字符前一个字符在 next 数组中对应的值找到模式串应该回退的位置,模式回到这个位置与当前的文本串位置继续比较,而不用回退文本串也不用回退到模式串的开头。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注