字符串匹配算法可视化

BF算法（暴力匹配算法）

BF算法说明

BF算法（Brute Force，暴力匹配算法）是最简单的字符串匹配算法：

  1. 设置主串S和模式T中的比较指针i和j（初始值：i = pos，j = 0）
  2. 比较S[i]与T[j]：
    • 若相等，则继续比较两者的下一个字符，直到j = M为止
    • 若不相等，i、j回溯，即i=i-j+1，j=0，重复过程
  3. 如果j=M，则匹配成功，返回值k=i-j；反之，匹配失败，返回值-1

KMP算法（Knuth-Morris-Pratt算法）

KMP算法说明

KMP算法是一种改进的字符串匹配算法，通过预处理模式串获得next数组，避免不必要的回溯：

  1. 在主串S和模式T中设置比较指针i和j（初始值：i=pos，j=0）
  2. 根据定义计算出模式T的各个位置j的next[j]数组的值
  3. 比较S[i]与T[j]：
    • 若相等，则继续比较两者的下一个字符，直到T的字符比较完（j=M）
    • 若不相等，则i不变，j回溯，即j=next[j]，重复比较
  4. 如果j=M，则匹配成功，返回值k=i-j；反之，匹配失败，返回值-1