首页 > 代码库 > KMP算法简单回顾

KMP算法简单回顾

前言

虽从事企业应用的设计与开发,闲暇之时,还是偶尔涉猎数学和算法的东西,本篇根据个人角度来写一点关于KMP串匹配的东西,一方面向伟人致敬,另一方面也是练练手,头脑风暴。我在自娱自乐,路过的朋友别太认真,嘿

背景

目标串: T(1…..n)

模式串: P(1…..m)

输出:搜索P在T中的位置 s,令 T(s…s+m-1) === P(1…m)

例如:

a g c t a g c a g c t a g c t g中查找a g c t g 返回 12(从1计数)

资料

资料太多了,我在此不准备进行深入分析整个推算过程,所以本篇文章只写给自己看

E文好理解能力好的直接去看原篇论文《Fast Pattern Matching in Strings》

主要思想参考这里:

字符串匹配的KMP算法(阮一峰)

主要实现参考这里:

http://blog.csdn.net/yearn520/article/details/6729426

http://biaobiaoqi.me/blog/2013/05/25/kmp-algorithm/

笨拙的大脑

我和很多普通人一样,对于此类问题,大脑中的第一反应时朴素暴力匹配法

  • 假设T从i处开始迭代索引
  • 比较失配时,使用回溯法,将P相对于T右移1位,然后T的迭代索引回溯到i+1,重新匹配
  • 缺陷:重复的移动操作,重复的比较匹配操作
  • 效率:移动操作为(n-m),比较操作为m,数量级O(n*m)

优化的KMP

KMP的核心思想是,利用模式串进行自我匹配,生成前缀数组,优化移动和匹配操作

  • 目标串无须回溯,只需要移动模式串即可,节省移动操作
  • 重复的匹配可以省略,节省了匹配操作,大概列两种极端的例子
  • 额外的空间开销O(m)(存储nexts数组),线性时间开销 O(n+m)

难点

算法的关键和难点在于计算前缀数组next[]

实现

  • 前缀数组next实现
static void SetPrefix(IList<char> pattern, int[] nexts){    nexts[0] = 0;    int m = pattern.Count;    for (int i = 0; i < m; i++)    {        int k = nexts[i - 1];        while (pattern[i] != pattern[k] && k != 0)        {            k = nexts[k - 1];        }        if (pattern[i] == pattern[k])            nexts[i] = k + 1;        else            nexts[i] = 0;    }}
  • KMP匹配方法实现
static IEnumerable<int> KMP(string text, string pattern){    int[] nexts = new int[pattern.Length];    int n = text.Length;    int m = pattern.Length;    SetPrefix(text.ToList(), nexts);    for (int i = 0, j = 0; i < n; i++)    {        while (j > 0 && text[i] != pattern[j])            j = nexts[j - 1];        if (text[i] == pattern[j])            j++;        if (j == m)            yield return i - m + 1;    }    yield break;}

结语

关于串匹配的算法还有很多,关于KMP的改进实现也有很多,时间和精力有限,以后有时间再深入!

KMP算法简单回顾