南孚电池网站建设,谷歌搜索引擎入口363,一起做网店入驻多少费用,如何优化网站关键词KMP算法
什么时KMP算法
KMP算法是一种改进的字符串匹配算法
由D.E.Knuth#xff0c;J.H.Morris和 V.R.Pratt提出的#xff0c;因此人们称它为克努特—莫里斯—普拉特操作#xff08;简称KMP算法#xff09;。
KMP的主要思想是当出现字符串不匹配时#xff0c;可以知道…KMP算法
什么时KMP算法
KMP算法是一种改进的字符串匹配算法
由D.E.KnuthJ.H.Morris和 V.R.Pratt提出的因此人们称它为克努特—莫里斯—普拉特操作简称KMP算法。
KMP的主要思想是当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容是KMP的重点也就是next数组。 next数组
next数组其实就是模式字符串模式串的前缀表prefix前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
要弄懂这些我们首先要了解一下几点问题 前缀包含首位字符但不会包含末位字符的子串后缀包含末位字符但不包含首位字符的子串。next数组的定义当主串与模式串的某一字符不匹配时模式串要回退的位置即在匹配过程中当一次匹配失败时下一次的匹配不不用冲模式串的第一位位开始匹配next[j]其值 第j位字符前面j-1位字符组成的子串的前后重合字符数1。 规律
next[j]的值每次最多增加1模式串的组后一位字符不影响next数组的结果
求next[j]数组的代码
/*** param {string[]} ch* param {int} length* param {int[]} next*/
function getNext(needle) {let next [];let j 0;next.push(j);for (let i 1; i needle.length; i) {while (j 0 needle[i] ! needle[j])j next[j - 1];if (needle[i] needle[j])j;next.push(j);}return next;
}例 j:1 2 3 4 5 6 p:a b a b a ?(模式串最后一位对next[j]数组是没有影响的)
next[j]:0 1 1 2 3 4 这里代码的主要思想是回溯且next[i]值的意义是第i位字符前的字符串的最长公共前后缀的长度1。
我们首先初始化next[1]0接着在next[1]基础上按顺序向后一一遍历那么我们要求next[i]的值时我们即已经知道next[i-1]的值假设它的值是j那么接意味着在数组中从第1位第i-2位的最长相等前后缀是j-1也就是说在模式串next[1] ~ next[i-2]的范围中1 ~ j-1和 i-j1 ~ i-2这两段长度为j-1的字符串是完全相等的。这是要分两种情况即第j位字符和第i-1位字符相等另一种是不相等
这时一旦第j位字符和第i-1位字符又相等的话那么next[i]的最长公共前后缀就是next[j-1]1,因为后缀多出来的一位字符和前缀多出来的一位字符相等这是最长公共前后缀自然要加1。但如果此时第j位字符和第i-1位字符不相等那么此时我们找第j位前的最长公共前后缀即next[j]-1此时我们可以知道next[0 ~ next[j-1]] next[next[j-1]-j1 ~ j] 。也就是说我们以j为分隔点先将模式串前后分为两段前后两段除追后一位不相等外其他完全相等那么前半部分满足这样的等式意味着后半部分同样满足着这样的等式即此时我们得到模式串的前i-1项又四段相等的子串第一段和第四段相等。即next[0 ~ next[j-1]] next[next[j]-i1 ~ i-2]。到了这里是否似曾相识没错这里就是回溯第一遍的结果那么再一次出现两种情况即第next[j-1]1项和i-1项时否相等 相等的话next[i]的最长公共前后缀就是刚刚比较的两段子串的长度加1即next[j-1]1。若不相等那么我们就需要再一次寻找相等的子串。此时将找到第next[j-1]位前的最长1公共前后缀。 依次循环知道找到相等或者即将回溯到下标为0时停止递归此时说明没有公共前后缀那么赋值为1也就是j1因为此时j为0。
KMP模式匹配算法
var strStr function (haystack, needle) {if (needle.length 0)return 0;let next getNext(needle);let j 0;for (let i 0; i haystack.length; i) {while (j 0 haystack[i] ! needle[j])j next[j - 1];if (haystack[i] needle[j])j;if (j needle.length)return (i - needle.length 1);}return -1;
};
