江苏建设人才网官方网站,学做网站论坛插件,平果信息网,网站首页快照应该怎么朴素匹配的逻辑#xff1a;
将原串的指针移动至本次发起点的下一个位置#xff08;b字符处#xff09;#xff1b;匹配串的指针移动至起始位置。尝试匹配#xff0c;发现对不上#xff0c;原串的指针会一直往后移动#xff0c;直到能够与匹配串对上位置。
如图#x…朴素匹配的逻辑
将原串的指针移动至本次发起点的下一个位置b字符处匹配串的指针移动至起始位置。尝试匹配发现对不上原串的指针会一直往后移动直到能够与匹配串对上位置。
如图
也就是说对于「朴素匹配」而言一旦匹配失败将会将原串指针调整至下一个「发起点」匹配串的指针调整至起始位置然后重新尝试匹配。
然后我们再看看KMP匹配过程 首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的前缀和后缀如果存在则跳转到前缀的下一个位置继续往下匹配 跳转到下一匹配位置后尝试匹配发现两个指针的字符对不上并且此时匹配串指针前面不存在相同的前缀和后缀这时候只能回到匹配串的起始位置重新开始
而KMP算法相对比朴素匹配的优化在于
因为KMP利用已匹配部分中相同的前缀和后缀来加速下一次的匹配。因为KMP的原串指针不会进行回溯没有朴素匹配中回到下一个发起点的过程
下面我们看代码
/*** param {string} haystack* param {string} needle* return {number}*/
var strStr function(haystack, needle) {// build nextArrlet next nextArr(needle)let i 0, j 0 // i表示遍历主串使用的指针 j表示遍历子串使用固定指针while(i haystack.length) {if(haystack[i] needle[j]) {ij}else if( j 0) {j next[j - 1]}else { // i是始终往前递增的 并不会回退i}if(j needle.length) { // 匹配成功 返回第一个匹配的indexreturn i - j}}return -1 // 匹配失败 返回-1
};
// kmp算法——计算子串对应的next数组
let nextArr function(arr) {let pre_len 0 // 当前公共前后缀长度let next [0] // 第一个元素默认是0let i 1while(i arr.length){ // 遍历一遍子串if(arr[pre_len] arr[i]) { // 公共前缀的最后一个位置的元素匹配当前遍历到的字符pre_len 1inext.push(pre_len) // 当前位置的next元素获取成功 i 向前推进 继续遍历}else { // 公共前缀的最后一个位置的元素不匹配当前遍历到的字符if(pre_len 0) { // 如果公共前后缀的长度是0 当前位置next的元素为0 i 向前推进 继续遍历i next.push(0)}else { // 当前公共前缀长度不为0 公共前缀长度-1 i不变 继续公共前缀最后一个位置的元素匹配当前遍历的字符pre_len next[pre_len - 1]}}}return next
}参考:
【宫水三叶】简单题学 KMP 算法最浅显易懂的 KMP 算法讲解
