首页 > 代码库 > KMP算法

KMP算法

 

1、概述

  KMP算法是一种改进的字符串匹配算法,关键在于利用匹配失败后的信息,尽量减少模式串与主串的次数。

2、算法原理

  举个简单的例子:主串为“BBC ABCDAB ABCDABCDABDE”,匹配串为“ABCDABD”

技术分享

 

  通常我们比较字符串,从头开始,第一个字符不匹配时,向后移匹配串。

技术分享

技术分享

 

  当匹配串与主串匹配时,比较主串和匹配串的下个字符 

技术分享

技术分享

  当匹配失败时,通常我们会会将匹配串后移一个字符,并重新开始匹配

技术分享

  这样的时间复杂度为O(N*M),而仔细观察,可以发现,匹配串中只有两个B,且都已经与主串,换句话说,主串在“ABCDAB”中不可能有第三个“B”,所以第一个“B”的下一个匹配点应该是在“ABCDAB”中的第二个B,即匹配串与主串匹配的第二个“B”

技术分享

  这样可以减少字符比较次数,那么这个后移位数应该如何确定,如何能最优呢

技术分享

  移动位数 = 已匹配的字符数 - 对应的部分匹配值

 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;

  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

参考资料

博客 《字符串匹配的KMP算法》http://kb.cnblogs.com/page/176818/

KMP算法