跳到主要内容

朴素匹配算法

朴素匹配算法如何工作？​

  • 对齐: 从文本串 T 的第一个字符开始与模式串 P 的第一个字符比较;
  • 继续: 字符相等则两个指针同时前进, 继续比较下一个字符;
  • 失败: 字符不等则把 T 的起点右移一格, P 回到开头重新比较;
  • 命中: P 全部匹配成功时, 返回匹配开始的下标;
  • 未命中: T 走到末尾仍未匹配, 返回 -1;
def bruteForce(T: str, p: str) -> int:
    n, m = len(T), len(p)
    i, j, start = 0, 0, 0
    while i < n and j < m:
        if T[i] == p[j]:
            i += 1
            j += 1
        else:
            i = start + 1
            start += 1
            j = 0
    return i - j if j == m else -1

朴素匹配算法的复杂度是多少？​

  • 平均: O(m + n);
  • 最坏: O(m × n), 例如文本串与模式串都由大量重复字符组成;
  • 问题: 失配后已匹配的前缀信息被丢弃, 每次都要从头比较;
  • 改进方向: 复用已匹配信息, 即 KMP 算法;