BF算法

• Brute Force，暴力匹配算法/朴素匹配算法

• 相关概念

  • 主串（长度n）
  • 模式串 （长度m）
  • 子串

• 思想：主串中，从0 - n-m，依次匹配

• 最坏时间复杂度：O(n*m)

• 常用原因

  • 模式串和主串不会太长，不匹配时可跳到下一位重新开始比较，效率比O(n*m)高很多
  • 思想简单，符合KISS设计原则

• BF算法实现

String.prototype.indexOf = function (pattern) {let str = thislet index = -1for (let i = 0; i < str.length - pattern.length + 1; i++) {let j = 0//子串与模式串比较for (; j < pattern.length; j++) {if (str[i + j] == pattern[j]) {continue} else {break}}if (j == pattern.length) {index = ibreak}}return index
}
var str = 'asdfghjklqwerty'
str.indexOf('sd')

RK算法

• Rabin-Karp

• 思想：用Hash算法，优化子串对比

• 原理

  • 根据i-1的hash值推导i的hash值
  • 无需遍历每个元素，提高Hash值的计算效率

• 实现

  • 使用二十六进制表示字符串，依次对应0-25
  • 举例：“dca” = 3 * 26³ + 2 * 26² + 0
  • 相邻子串hash值公式：h[i] = 26*(h[i-1]-26^m-1*S[i-1]-‘a’)+S[i+m-1]-‘a’

• 时间复杂度

  • 计算子串Hash值，O(n)
  • 模式串与子串Hash比较，O(1)

• 效果

  • 模式串很长时，二十六进制的Hash值无法表示
  • 无散列冲突问题
  • 只能计算小写字母的

• 改进

  • 优化哈希函数，缩小取值范围
  • 针对hash冲突，直接对比子串

• RK算法一：二十六进制表示hash值

function indexOf(str, pattern) {let index = -1let m = pattern.length//存储26d的m内次方，便于取值let arr = []for (let i = 0; i < m; i++) {arr[i] = Math.pow(26, i)}let pHash = 0      //模式串hashsHash = 0           //子串hashfor (let i = 0; i < m; i++) {pHash += get26Num(pattern[i]) * arr[m - 1 - i]sHash += get26Num(str[i]) * arr[m - 1 - i]}if (pHash == sHash) {index = 0}for (let i = 1; i < str.length - pattern.length + 1; i++) {if (index != -1) breaksHash = 26 * (sHash - arr[m - 1] * get26Num(str[i - 1])) + get26Num(str[i + m - 1])if (sHash == pHash) {index = i}}return indexfunction get26Num(letter) {return letter.charCodeAt(0) - 97}
}
var str = 'abcdefg'
indexOf(str, 'cdefg')        //2
indexOf(str, 'cdefa')       //-1

• RK算法二：范围小的hash函数 + 解决散列冲突

//hash函数：每个字母对应一个素数
function indexOf(str, pattern) {var prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]let index = -1let m = pattern.lengthlet pHash = 0      //模式串hashsHash = 0           //子串hashfor (let i = 0; i < m; i++) {pHash += getPrimeNum(pattern[i])sHash += getPrimeNum(str[i])}isFind(0)for (let i = 1; i < str.length - pattern.length + 1; i++) {if (index != -1) break//根据第i-1个元素的hash求第i个元素的hashsHash = sHash - getPrimeNum(str[i - 1]) + getPrimeNum(str[i + m - 1])isFind(i)}return indexfunction isFind(i) {if (sHash == pHash) {//逐个匹配，解决散列冲突for (let j = i; j < i + m; j++) {if (str[j] != pattern[j - i]) {return}}index = i}}function getPrimeNum(letter) {return prime[letter.charCodeAt(0) - 97]}
}
var str = 'abcdefg'
indexOf(str, 'cdefg')        //2
indexOf(str, 'cdefa')       //-1