bf算法（Brute Force暴力匹配算法）

  • 主串，长度为n
  • 模式串，长度为m

  • 比较n-m+1次，每次比较m个字符串，复杂度为n*m

    rk算法

  • 是bf算法的升级版

  • 对主串的n-m+1个子串进行hash运算，得到hash值，再跟模式串的hash进行对比，因为hash是数字，因此速度较快

  • 复杂度为n

    bm算法（boyer moore）

  • 在bf算法的基础上，遇到不匹配的子串，直接跳过不匹配的部分

  • 坏字符串规则
    • 子串和模式串倒着匹配
    • 复杂度n/m

  • 好后缀规则

    • 滑动规则

      kmp算法