Wildcard字符串分析算法

title: Wildcard字符串分析算法 id: 1de068f425d98e7cc2789a395f8dec94 tags: [] date: 2000/01/01 00:00:00 updated: 2023/03/04 19:29:12 isPublic: true --#|[分隔]|#--

Wildcard字符串分析算法

适用场景

给定一个长字符串，再给定包含*和?的正则短字符串，判断这个长字符串是否包含正则短字符串。

算法原理

和KMP算法类似，但需要先把短字符串以 * 为分隔，分成几段。

比如 短字符串：ab*cd*cd，那么只要长字符串的开头两位为 ab，最后两位为ef，中间那部分包含一个cd，就是符合的，比如一下这几个长字符串都是符合的：

abcdcd、ab0000cdcd、ab0000cd0000cd

但要注意，长字符串 abcd 是不符合的。

最后就是 ? 的处理，这个比较简单，因为它表示的是有一位任意的字母，哪怕是空格也符合，在对比时多一个判断即可。

代码实现

/**
 * Wildcard字符串分析算法
 * 传入长和短字符串, 返回长字符串是否符合短字符串定义的格式
 * 短字符串中可能包含 * 和 ?
 * @param {String} longStr 
 * @param {String} shortStr 
 */
function Wildcard(longStr, shortStr) {
  let startCount = 0 // * 的个数

  for (let i = 0; i < shortStr.length; i++) {
    if (shortStr[i] === '*') startCount++
  }

  // 没有 *, longStr, shortStr 需要是全等(注意里面有?匹配符)
  if (!startCount) {
    // 长度不同
    if (shortStr.length !== longStr.length) {
      return false
    }
    for (let i = 0; i < shortStr.length; i++) {
      if (longStr[i] !== shortStr[i] && shortStr[i] !== '?') {
        return false
      }
    }
    return true
  } else { // 包含 * , 开始遍历处理

    let i = 0 // 取的 shortStr 的索引值
    let lastIndex = i // 正则的 exec 的 lastIndex, 后面会用

    // 判断第一个 * 之前的字符
    {
      for (; shortStr[i] !== '*'; i++) {
        if (longStr[i] !== shortStr[i] && shortStr[i] !== '?') {
          return false
        }
      }
      lastIndex = i // 更新一下, 让后面校验 longStr 时, 从 i 这个索引开启(i之前的部分,都是第一个星号之前的,已经匹配完了)
    }

    { // 判断中间部分的匹配
      for (let p = 0; p < startCount - 1; p++) {
        ++i // 注意, 经历了上面和上一个循环的步骤 shortStr[i] === '*', 所以 i 需要先加1

        let subshortStr = '' // shortStr 中, 被 * 分隔的字符串片段
        // shortStr 的当前这一项不是 *, 拼接取来, 用来下面的匹配查找
        while (shortStr[i] !== '*' && i < shortStr.length) {
          subshortStr += shortStr[i]
          i++
        }

        let Reg = new RegExp(subshortStr.replace(/\?/g, '[\\s\\S]'), 'g')

        Reg.lastIndex = lastIndex
        // 没有匹配上
        if (!Reg.exec(longStr)) {
          return false
        }

        // 这个片段匹配上了, 更新一下 lastIndex, 给下一个循环备用
        lastIndex = Reg.lastIndex
      }

      { // 判断最后一个 * 后面的字符, 必须全字符匹配

        ++i // 注意, 经历了上面和上一个循环的步骤 shortStr[i] === '*', 所以 i 需要先加1
        // 最后一个 * 后面还有东西
        if (i < shortStr.length) {

          for (let j = 1; shortStr[shortStr.length - j] !== '*'; j++) {
            let longStrIndex = longStr.length - j
            if (longStrIndex < lastIndex) {
              // 和上面已经比过的字符重叠了
              return false
            }
            if (longStr[longStr.length - j] !== shortStr[shortStr.length - j] && shortStr[shortStr.length - j] !== '?') {
              return false
            }
          }
        }
      }
      // 判断完成, 能走到这儿, 匹配通过
      return true
    }
  }
}

console.log(Wildcard('sfsff', 'sf?f'))