< Back

子字符串查询

字符串的一种基本操作就是子字符串查询：给定一段长度为N的文本和一个长度为M的模式（pattern）字符串，然后在文本中找到一个和该模式相符的子字符串。

img

暴力查找

两个for循环，外面的扫描文本，里面的扫描pattern，一个个字符比对，只要发现不匹配的就结束内循环，然后外面循环指针加1，继续从文本下一个字符开始匹配，简单粗暴。

class Naive {
  public search(pat: string, txt: string) {
    const M = pat.length
    const N = txt.length
    for (let i = 0; i <= N - M; i++) {
      let j: number = 0
      for (j = 0; j < M; j++) {
        if (txt.charAt(i + j) !== pat.charAt(j)) {
          break
        }
      }
      if (j === M) {
        return i
      }
    }
    return N
  }
}

最坏情况下需要～NM次字符比较

还有另一个版本的暴力查找（显示回退），i和j一同成长，等到不匹配的时候双双回退。

class Naive1 {
  public search(pat: string, txt: string) {
    let i,
      M = pat.length
    let j,
      N = txt.length
    for (i = 0, j = 0; i < N && j < M; i++) {
      if (txt.charAt(i) === pat.charAt(j)) {
        j++
      } else {
        i -= j
        j = 0
      }
    }
    return j === M ? i - M : N
  }
}

const txt = 'abcaaccaa'

console.log(new Naive().search('caa', txt)) // 2
console.log(new Naive1().search('caa', txt)) // 2

KMP

他要解决的问题是，在发生不匹配的情况回退的时候，不用完全整个的回退，如下图的情况，当字母表只有两个字符的时候，发现i指向的字符不匹配的时候，按暴力查找的回退方式，其实浪费很多时间。而KMP要解决的就是要如何“回退”到最合适的位置。

img

DFA

他用了一个叫做**确定有限状态自动机（DFA）**的东西来思考这个问题，这个东西好像是离散数学里面的？我以前也没听过这个，花了好一些时间，反正跟自己算是说得通了吧🤷‍♂️。首先，每一个模式都会有一个固定的dfa，比如下图的模式为ABABAC，书上的构造过程我没有看太明白，然后找到了一个视频，dfa的构造过程大致是这样的：

  • 最开始状态为0：此时只有遇到字符A的时候才会前进到状态1，遇到BC都是原地不动，还是0

  • 状态1: 遇到B前进到2，而遇到A的时候还是1（这时还是可以光靠看就能写出来）

  • 状态2: 遇到BC的时候应该回到哪个状态？

    这个时候再回到子字符串查找中来，想象一下，如果你在ABA中的最后一个字符没有匹配的情况下，暴力查找此时会怎么走？

    会i++，然后开始将文本中的[i, j]字符开始和模版字符中从0索引位置（因为j会直接重置为0）逐个进行匹配查找，这里有一个隐含的或者容易忽视的信息就是此时的[i, j]其实就对应模式字符串中的[1, j]的字符，因为是在j+1处匹配失败，那就意味这这之前的字符都是匹配的，因此可以换句话说其实就是将模式字符串中的[1, j]的字符和模式字符串进行匹配。

    对应此时的情况就是将字符B开始和模版中的索引0字符A进行匹配。对应的过程其实就是将B再丢进dfa中，从状态0开始，遇到B，会回到状态0，那么就把状态0时候遇到BC的值复制过来，这里我们将状态0称之为重启状态。

    为什么可以这么做呢？因为像上面说的，暴力查找完全回退进行的操作和这里将[1,j]（在j+1遇到不匹配）的字符丢进状态机的操作是一样的。然后通过这种之前进行过的操作给保存起来，直接查表就可以了，省掉了一些重复的操作。

    这确实是一个非常巧妙的思想，但是也确实不是很好理解。我看了一些文章讲前缀和后缀的最长公共部分啥的，那样确实很好理解，更直观，但是要我始终无法把dfa的构造和前后缀啥的联系起来，所以直到我看到了那个视频，看到他提到的这种dfa构造方式，然后又想到了暴力查找的执行过程，发现了两者之间的一些联系，才开始感觉make sense。

  • 状态3:遇到AC应该回到哪个状态？

    和状态2时的运作方式一样，我们只要把[1, j]的字符再丢到我们的dfa里面走一遍，看最终会留在哪个状态，就把那个状态的值给复制过来即可。这时的[1, j]字符为BA，0遇到B为0，然后再遇到A，到达状态1，因此把状态1的值复制过来。之后的也依此类推。

img

如果用代码构造dfa

书中给出了如下短小精悍的代码来构造dfa，这就是另外一个巧妙的地方了，一开始看一脸懵逼但是一旦知道了上面的构造方式就比较好理解了。

this.dfa[pat.charCodeAt(0)][0] = 1
for (let X = 0, j = 1; j < M; j++) {
  for (let c = 0; c < R; c++) {
    this.dfa[c][j] = this.dfa[c][X]
  }
  this.dfa[this.pat.charCodeAt(j)][j] = j + 1
  X = this.dfa[this.pat.charCodeAt(j)][X]
}

我们已经知道构造dfa的步骤就是：

  • 遇到匹配字符就前进一个状态
  • 遇到不匹配字符就直接将重启状态中的值复制过来

那么关键在于如何找到重启状态？上面我们找重启状态的方式是将[1, j]的字符逐个丢到状态机里看最终落到哪个状态。

他这里用了一个X来表示重启状态，我们思考这个X是怎么走的，X初始化为0，然后随着j的前进，开始将j丢给dfa，知道循环结束的时候会把哪些字符丢给dfa去更新X呢？[1, M-1]区间的字符，没错更新X的这个过程其实就是上面说的将[1, j]的字符逐个丢到状态机里看最终落到哪个状态的过程。（可能需要一点想象空间吧……

img
img
class KMP {
  private pat: string
  private dfa: number[][]

  constructor(pat: string) {
    this.pat = pat
    const M = pat.length
    const R = 256
    this.dfa = new Array(R).fill(0).map(_ => new Array(M).fill(0))
    this.dfa[pat.charCodeAt(0)][0] = 1
    for (let X = 0, j = 1; j < M; j++) {
      for (let c = 0; c < R; c++) {
        this.dfa[c][j] = this.dfa[c][X]
      }
      this.dfa[this.pat.charCodeAt(j)][j] = j + 1
      X = this.dfa[this.pat.charCodeAt(j)][X]
    }
  }

  public search(txt: string) {
    let i: number, j: number, N = txt.length, M = this.pat.length
    // i永不回头，然后通过查表来更新j
    for (i = 0, j = 0; i < N && j < M; i++) {
      j = this.dfa[txt.charCodeAt(i)][j]
    }
    if (j === M) return i - M
    else return N
  }
}

const kmp = new KMP('caa');
console.log(kmp.search('abcaaccaa'))  // 2
console.log(kmp.search('epqacaaac'))  // 4

Boyer-Moore

这个算法比KMP就容易理解多了，查找过程如下图所示，和之前不同的是，这里是从右向左扫描。比如一开始比较最后一个字符，N（文本字符）和E（模式字符）不匹配，那么就找到N在模式字符串中最右边的N在哪个位置，这里是0，所以直接把模式字符串右移对准N，依此类推进行下去。

img

因此这里首先需要得到一个保存了所有字符在模式字符串中最右的索引的数组。

class BoyerMoore {
  private right: number[]
  private pat: string

  constructor(pat: string) {
    this.pat = pat
    const M = pat.length
    const R = 256
    this.right = new Array(R).fill(0)

    for (let c = 0; c < R; c++) {
      this.right[c] = -1
    }
    for (let j = 0; j < M; j++) {
      this.right[pat.charCodeAt(j)] = j
    }
  }

  public search(txt: string) {
    const N = txt.length
    const M = this.pat.length
    let skip: number
    for (let i = 0; i <= N - M; i += skip) {
      skip = 0
      for (let j = M - 1; j >= 0; j--) {
        if (this.pat.charAt(j) !== txt.charAt(i + j)) {
          skip = j - this.right[txt.charCodeAt(i + j)]
          if (skip < 1) skip = 1
          break
        }
      }
      if (skip === 0) return i
    }
    return N
  }
}

const bm = new BoyerMoore('caa')
console.log(bm.search('abcaaccaa')) // 2
console.log(bm.search('epqacaaac')) // 4

总结

暴力算法在实现简单，且一般情况下都工作良好（Java的String类型的indexOf()就是使用的暴力算法），KMP能保证线性级别的性能且不需要在正文中回退，Boyer-Moore算法的性能在一般情况下都是亚线性级别（可能是线性级别的M倍）

img

本节代码：https://github.com/Yuijam/algorithms-note/tree/main/string/substring