字符串匹配KMP 字符串匹配KMP

本文内容学习自字符串匹配的KMP算法

如果有一个字符串BBC ABCDAB ABCDABCDABDE ，要查找里面是否有搜索串 ABCDABD。
那实现代码最简单的方法就是 两层循环 ，以此比较。

文章图片
字符串比较步骤

1 字符串的第一位和搜索串的第一位不同，搜索串后移一位，继续比较
2 字符串的第一位和搜索串的第一位相同，比较字符串的第二位和搜索串的第二位是否相同。直到全部相同，查找结束。否则搜索串后移一位，继续比较

这样做法肯定能实现，但是太耗性能
KMP
kmp 算法的优点就是简化了比较的次数，不用逐步比较
字符串比较步骤

1 字符串的第一位和搜索串的第一位不同，搜索串后移一位，继续比较（与上面相同）
2 字符串的第一位和搜索串的第一位相同，比较字符串的第二位和搜索串的第二位是否相同。直到全部相同，查找结束。否则搜索串后移（这里做了优化），继续比较

文章图片
字符串的第一位和搜索串的第一位不同，搜索串后移一位继续比较。。。直到

文章图片
这里已经有六位相同

这里已经有六位数是相同的了，如果按照普通的比较，只能后移一位重新比较
这里 kmp 算法会借助已匹配的这一位计算后移的位数

kmp 位移数计算

文章图片
对已匹配的字符串计算步骤按照一般方法是这样比较的

文章图片
kmp 位移数会计算移动步数
我们的目的是找到搜索串全匹配的位置，可以这样优化位移数

字符串已经有6个字符串与 搜索串中的6个字符串相同，只要关心搜索串中已匹配的6个字符串即可
- 假设搜索串中已匹配的6个字符串全不相同，就可以移动 全部的相同字符串
  
  文章图片
- 如果搜索串中已匹配的6个字符串有相同的，就可以移动 部分字符串

文章图片
因此：

位移数 = 已匹配的长度 - 元素中重复出现的长度

步骤图如下

文章图片
步骤图.png 匹配数代码实现建立搜索串对应长度中的重复字符串

let startTimestamp=new Date().getTime() let string = 'BBC ABCDAB ABCDABCDABDE' let keyString = 'ABCDABD' let arr = [] // 建立搜索关键字数组 let findRelation = function() { let searchArr = [] let relationArr = [] for (let i = 0; i < keyString.length; i++) { searchArr.push(keyString.slice(0, i+1)) } for (let i = 0; i < searchArr.length; i++) { let sameFlag = 0 // 共有长度计数 if (searchArr[i].length === 1) { // 字符串长度为1时，共有长度为0 relationArr.push({goal: searchArr[i], sameFlag: sameFlag}) }else { let string =searchArr[i] let frontArr = [] let backArr = [] // 处理正反两个数组，并且比较，获取共有数据长度 for (let i = 0; i < string.length-1; i++) { frontArr.push(string.slice(0, i+1)) backArr.push(string.slice(-(i+1))) } for (let i = 0; i < frontArr.length; i++) { if(frontArr[i] === backArr[i]) { sameFlag = backArr[i].length } } relationArr.push({goal: searchArr[i], sameFlag: sameFlag}) } } return relationArr }