家庭网站建设,90自己做网站,做玻璃的网站,有用dojo做的网站吗1.KMP算法本质上就是对朴素匹配算法(BF)的一个优化#xff0c;减少朴素匹配算法中不必要匹配的次数#xff0c;核心代码和朴素匹配算法差不多#xff0c;BF是移动字串逐个字符匹配#xff0c;每次模式串(子串)匹配只移动一个字符单位#xff0c;而KMP算法是每次模式串匹配…1.KMP算法本质上就是对朴素匹配算法(BF)的一个优化减少朴素匹配算法中不必要匹配的次数核心代码和朴素匹配算法差不多BF是移动字串逐个字符匹配每次模式串(子串)匹配只移动一个字符单位而KMP算法是每次模式串匹配移动j-next个字符单位next存放在next[]数组里j为匹配失败的那个字符位置。
2.为什么KMP算法可以减少不必要的匹配次数?
利用了之前已经匹配过的字符前缀信息比如下图:(第一行为主串,第二行为模式串)
可以看到在第七个位置匹配失败,只需要满足主串a字符前面从右边开始从左往右数的字符串 等于 模式串c字符前面从左边开始从左往右数的字符串。其最大字符个数就为next的值这里就是next[j]4,接着将模式串移动到模式串j4(也就是jnext[j])的位置。如下图:
从两图可以看到模式串移动了2个单位而不是像BF那样每次移动一个单位。 注意:
模式串移动的过程中i是不会变的。字符匹配的下标可以从1开始也可以从零开始。
接下来就是确定next数组的值(next数组计算方法是KMP精华的部分)能够确保每次模式串移动的单位。
考试时的做法
以前准备数据结构考试计算next[]的时候只要计算模式串从字符前从右边开始从左往右数 等于 模式串字符前面从左边开始从左往右数 的最大字符个数(不包括模式串本身)。 具体计算过程:将模式串的前缀都抽出来,如下图。 为什么只需要利用模式串 因为 主串和模式串匹配失败时匹配失败字符的前缀内容是一样的所以之前的主串a字符前面从右边开始从左往右数的字符串 等于 模式串c字符前面从左边开始从左往右数的字符串可以替换为模式串c字符前面从右边开始从左往右数的字符串 等于 模式串c字符前面从左边开始从左往右数的字符串
编程的方法求next。
说白了就是模式串自己与自己匹配比较其开头和结尾即可得到最大 相同字符的个数 即可下标建议都从1开始且next[1]0因为模式串本身并不算所以下图直接从第二个元素开始比。目的是求next[i[的值举例流程如下图 参考文章:KMP
