单模式串字符串匹配

给定单个字符串S(长度m),查找目标模式串pattern(长度n)。 这个问题常见的会是采用朴素匹配,

朴素匹配实际为暴力匹配(BrueForce)本文讲述的是KMP算法, 维基百科 维基百科里面讲述的较详细, 就如下几个重点本文讲述下。

KMP相对朴素匹配

本质上是在朴素匹配上做了一个剪枝, 朴素匹配在S串上依次对pattern串进行比较,复杂度O(m*n), 而KMP逻辑会进行跳过,复杂度O(m+n)。

KMP关键点

  • 理解字符串的真前缀(proper preffix)、真后缀(proper suffix)。不包含本身的前缀或者后缀,如snake的真前缀s,sn,sna,snak。
  • 真前缀和真后缀的相同意味着什么,这个理解清楚了就是KMP对比跳过的剪枝逻辑。理解见代码
  • next()函数表及实现
  • 根据next()函数遍历目标串S

代码演示:

1
2

代码文件:C7QuickSort.java

总结

  • “KMP关键点” 前两点是理解关键,后两点是实现
  • AC自动状态机本质来说是KMP的一个多模式演变, 多模串仅一个分支的话就是KMP

版权声明:本文为博主原创文章,未经允许不得转载。