JS实现KMP算法

墨蓝 2023-10-10 09:51 4阅读 0赞

**KMP算法和BM算法**

KMP是前缀匹配和BM后缀匹配的经典算法，看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。  
前缀匹配是指：模式串和母串的比较从左到右，模式串的移动也是从 左到右  
后缀匹配是指：模式串和母串的的比较从右到左，模式串的移动从左到右。

**KMP**

KMP也是一种优化版的前缀算法，之所以叫KMP就是Knuth、Morris、Pratt三个人名的缩写，对比下BF那么KMP的算法的优化点就在“每次往后移动的距离”它会动态的调整每次模式串的移动距离，BF是每次都+1，KMP则不一定。

移动位数 = 已匹配的字符数 - 对应的部分匹配值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]  
**KMP实现（一）----匹配表**

**回退算法**

//子循环
    for (var j = 0; j < searchLength; j++) {
        
        //如果与主串匹配
        if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        
            //如果是匹配完成
            if (j == searchLength - 1) {
        
              result = i - j;
              break;
            } else {
        
              //如果匹配到了，就继续循环，i++是用来增加主串的下标位
              i++;
            }
        } else {
        
          //在子串的匹配中i是被叠加了
          if (j > 1 && part[j - 1] > 0) {
        
            i += (i - j - part[j - 1]);
          } else {
        
            //移动一位
            i = (i - j)
          }
          break;
        }
    }

红色标记的就是KMP的核心点 **next的值 = 已匹配的字符数 - 对应的部分匹配值**

完整的KMP算法

<!doctype html>
    <div id="test2">
      <div>
        <script type="text/javascript">
    
    
          function kmpGetStrPartMatchValue(str) {
        
            var prefix = [];
            var suffix = [];
            var partMatch = [];
            for (var i = 0, j = str.length; i < j; i++) {
        
              var newStr = str.substring(0, i + 1);
              if (newStr.length == 1) {
        
                partMatch[i] = 0;
              } else {
        
                for (var k = 0; k < i; k++) {
        
                  //取前缀
                  prefix[k] = newStr.slice(0, k + 1);
                  suffix[k] = newStr.slice(-k - 1);
                  if (prefix[k] == suffix[k]) {
        
                    partMatch[i] = prefix[k].length;
                  }
                }
                if (!partMatch[i]) {
        
                  partMatch[i] = 0;
                }
              }
            }
            return partMatch;
          }
    
    
    
          function KMP(sourceStr, searchStr) {
        
            //生成匹配表
            var part = kmpGetStrPartMatchValue(searchStr);
            var sourceLength = sourceStr.length;
            var searchLength = searchStr.length;
            var result;
            var i = 0;
            var j = 0;
    
            for (; i < sourceStr.length; i++) {
         //最外层循环，主串
    
              //子循环
              for (var j = 0; j < searchLength; j++) {
        
                //如果与主串匹配
                if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        
                  //如果是匹配完成
                  if (j == searchLength - 1) {
        
                    result = i - j;
                    break;
                  } else {
        
                    //如果匹配到了，就继续循环，i++是用来增加主串的下标位
                    i++;
                  }
                } else {
        
                  //在子串的匹配中i是被叠加了
                  if (j > 1 && part[j - 1] > 0) {
        
                    i += (i - j - part[j - 1]);
                  } else {
        
                    //移动一位
                    i = (i - j)
                  }
                  break;
                }
              }
    
              if (result || result == 0) {
        
                break;
              }
            }
    
    
            if (result || result == 0) {
        
              return result
            } else {
        
              return -1;
            }
          }
    
          var s = "BBC ABCDAB ABCDABCDABDE";
          var t = "ABCDABD";
    
    
          show('indexOf', function () {
        
            return s.indexOf(t)
          })
    
          show('KMP', function () {
        
            return KMP(s, t)
          })
    
          function show(bf_name, fn) {
        
            var myDate = +new Date()
            var r = fn();
            var div = document.createElement('div')
            div.innerHTML = bf_name + '算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
            document.getElementById("test2").appendChild(div);
          }
    
    
        </script>
      </div>
    </div>

**KMP（二）----next算法**  
第一种kmp的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样。

生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可。

完整的KMP.next算法

<!doctype html>
    <div id="testnext">
      <div>
        <script type="text/javascript">
    
          function next(str) {
        
            var prefix = [];
            var suffix = [];
            var partMatch;
            var i = str.length
            var newStr = str.substring(0, i + 1);
            for (var k = 0; k < i; k++) {
        
              //取前缀
              prefix[k] = newStr.slice(0, k + 1);
              suffix[k] = newStr.slice(-k - 1);
              if (prefix[k] == suffix[k]) {
        
                partMatch = prefix[k].length;
              }
            }
            if (!partMatch) {
        
              partMatch = 0;
            }
            return partMatch;
          }
    
          function KMP(sourceStr, searchStr) {
        
            var sourceLength = sourceStr.length;
            var searchLength = searchStr.length;
            var result;
            var i = 0;
            var j = 0;
    
            for (; i < sourceStr.length; i++) {
         //最外层循环，主串
    
              //子循环
              for (var j = 0; j < searchLength; j++) {
        
                //如果与主串匹配
                if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        
                  //如果是匹配完成
                  if (j == searchLength - 1) {
        
                    result = i - j;
                    break;
                  } else {
        
                    //如果匹配到了，就继续循环，i++是用来增加主串的下标位
                    i++;
                  }
                } else {
        
                  if (j > 1) {
        
                    i += i - next(searchStr.slice(0, j));
                  } else {
        
                    //移动一位
                    i = (i - j)
                  }
                  break;
                }
              }
    
              if (result || result == 0) {
        
                break;
              }
            }
    
    
            if (result || result == 0) {
        
              return result
            } else {
        
              return -1;
            }
          }
    
          var s = "BBC ABCDAB ABCDABCDABDE";
          var t = "ABCDAB";
    
    
          show('indexOf', function () {
        
            return s.indexOf(t)
          })
    
          show('KMP.next', function () {
        
            return KMP(s, t)
          })
    
          function show(bf_name, fn) {
        
            var myDate = +new Date()
            var r = fn();
            var div = document.createElement('div')
            div.innerHTML = bf_name + '算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
            document.getElementById("testnext").appendChild(div);
          }
    
        </script>
      </div>
    </div>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190924181219565.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70