【Q077】28. 实现 strStr()

/**
 * sunday 匹配算法
 *
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {

  if (needle.length > haystack.length) {
    return -1
  }

  if (needle == '') {
    return 0
  }

  let dic = calShiftMat(needle)

  let idx = 0

  while (idx + needle.length <= haystack.length) {
    let subStr = haystack.substring(idx, idx + needle.length)

    if (subStr === needle) {
      return idx
    } else {
      if (idx + needle.length >= haystack.length) {
        return -1
      }

      let nextFirstChar = haystack[idx + needle.length]

      if (dic[nextFirstChar]) {
        idx += dic[nextFirstChar]
      } else {
        idx += dic['ot']
      }
    }
  }

  return -1
};

function calShiftMat(str) {
  let offset = {}
  for (let i = 0; i < str.length; i++) {
    offset[str[i]] = str.length - i
  }

  offset['ot'] = str.length + 1

  return offset
}

字符串匹配的KMP算法

字符串匹配的Boyer-Moore算法

silver-hands / sss

【Q077】28. 实现 strStr() #77