字符串匹配的KMP算法-JavaScript

阳光穿透心脏的1/2处 2022-11-26 05:58 73阅读 0赞

### KMP ###

##### 学习资源 #####

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html

##### JavaScript代码实现 #####

// 1、部分匹配值的计算
    // 对传入的字符串，前缀、后缀去重，获取最大长度
    function prefix_suffix (str) { 
      const prefix = []
      const suffix = []
      const obj = { }
      let num = 0
      for (let i = 1; i < str.length; i++) { 
        const pre = str.slice(0, i)
        const suf = str.slice(i)
        prefix.push(pre)
        suffix.push(suf)
        if (!obj[pre]) { 
          obj[pre] = 1
        } else { 
          obj[pre] = pre.length
          num = Math.max(obj[pre], num)
        }
        if (!obj[suf]) { 
          obj[suf] = 1
        } else { 
          obj[suf] = suf.length
          num = Math.max(obj[suf], num)
        }
      }
      return num
    }
    
    // 2、部分匹配表，调用prefix_suffix方法计算出匹配值，返回对应表
    function matching (str) { 
      const length = str.length
      const list = []
      for (let i = 0; i < length; i++) { 
        list.push(prefix_suffix(str.slice(0, i)))
      }
      return list
    }
    
    // 3、定位，计算出两个字符串相同部分
    function position (source, temp) { 
      let index = 0
      for (let i = 0; i < temp.length; i++) { 
        if (source[i] === temp[i]) { 
          index = i + 1
        }
      }
      return index
    }
    
    // 4、循环调用position、matching进行数据匹配
    function contrast (source, temp) { 
      const sourceLength = source.length;
      const tempLength = temp.length
      const indexArr = matching(temp)
      let resolve = false
      let index = null
      for (let i = 0; i < sourceLength - tempLength;) { 
        let num = position(source.slice(i), temp)
        if (num === tempLength) { 
          index = i + num
          resolve = true
          break
        } else { 
          i += ((num - indexArr[num]) || 1)
        }
      }
      console.log(resolve, index);
    }
    contrast('BBC ABCDAB ABCDABCDABDE', 'ABCDABD')