Naive matching:最直白的对齐与 comparison
要在 text 里找 pattern,最直接的办法是反复执行同一套流程:
- 把 pattern 对齐到 text 的某个起点 offset(先从 0 开始)。
-
从左到右逐字符比
text[offset+j]与pattern[j]。 - 全部相等 → 在 offset 处命中。中途失配 → 放弃这个对齐。
- 把 offset 右移一格,重复以上比较,直到 pattern 滑出 text 末尾。
它一定正确,但慢:每次失配都把之前比对的进度全部丢掉、退回去从头再比。下面点「下一步」走一遍,留意右下角的 comparison 计数器——它就是后续算法要削减的成本。
最坏情况: 试试 text = aaaaaab、pattern = aaab:几乎每个对齐位置都要比到最后一个字符才失配,comparison 次数接近
。真实文本里这种「长前缀反复出现」并不罕见——这正是 KMP 与 Boyer-Moore 要消除的开销。