串匹配

BF算法

基本思想：

模式串字符依次与主串信息比较。匹配不成功时，模式串后移一个字符，并重头开始与主串比较

如：S: cabcac T:cac

c a b c a c
c a c
  c a c
    c a c
      c a c

时间复杂度：

O(mn)（m，n分别为主串和模式串的长度）

KMP算法

基本思想：

模式串字符依次与主串信息比较。匹配不成功时，模式串根据next数组跳转，并在不匹配处开始与主串比较

如：设主串S=“ababaababcb”,模式串T=”ababc”

i，j分别作为主串的下标和模式串下标

时间复杂度：

O(m+n)（m，n分别为主串和模式串的长度）