← 字符串查找算法 · naive matching / KMP / Boyer-Moore / Rabin-Karp / Naive matching:最直白的对齐与 comparison 待审核 1 / 13
brute-force · 逐位置逐字符

Naive matching:最直白的对齐与 comparison

要在 text 里找 pattern,最直接的办法是反复执行同一套流程:

  • 把 pattern 对齐到 text 的某个起点 offset(先从 0 开始)。
  • 从左到右逐字符比 text[offset+j]pattern[j]
  • 全部相等 → 在 offset 处命中。中途失配 → 放弃这个对齐。
  • 把 offset 右移一格,重复以上比较,直到 pattern 滑出 text 末尾。

它一定正确,但:每次失配都把之前比对的进度全部丢掉、退回去从头再比。下面点「下一步」走一遍,留意右下角的 comparison 计数器——它就是后续算法要削减的成本。

最坏情况: 试试 text = aaaaaab、pattern = aaab:几乎每个对齐位置都要比到最后一个字符才失配,comparison 次数接近 n×mn\times m。真实文本里这种「长前缀反复出现」并不罕见——这正是 KMPBoyer-Moore 要消除的开销。