字符串匹配的KMP算法

标签: 字符串 匹配 kmp | 发表时间:2013-08-28 09:12 | 作者:
分享到:
出处:http://kb.cnblogs.com/

   字符串匹配是计算机的基本任务之一。

  举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

  许多算法可以完成这个任务, Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。

  这种算法不太容易理解,网上有很多 解释,但读起来都很费劲。直到读到 Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。

  1.

  首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

  2.

  因为B与A不匹配,搜索词再往后移。

  3.

  就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

  4.

  接着比较字符串和搜索词的下一个字符,还是相同。

  5.

  直到字符串有一个字符,与搜索词对应的字符不相同为止。

  6.

  这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

  7.

  一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

  8.

  怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

  9.

  已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

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

  因为 6 - 2 等于4,所以将搜索词向后移动4位。

  10.

  因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

  11.

  因为空格与A不匹配,继续后移一位。

  12.

  逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

  13.

  逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

  14.

  下面介绍《部分匹配表》是如何产生的。

  首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

  15.

  "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"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。

  16.

  "部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

相关 [字符串 匹配 kmp] 推荐:

字符串匹配的KMP算法

- - 博客园_知识库
   字符串匹配是计算机的基本任务之一.   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD".   许多算法可以完成这个任务, Knuth-Morris-Pratt算法(简称KMP)是最常用的之一.

字符串匹配 KMP 算法 Java实现

- - ITeye博客
字符串匹配过程中,如果使用蛮力算法,效率非常的差,在此介绍一种较为高效的匹配算法KMP算法. 其主要思想是从匹配的模版去分析,即去分析Pattern串的自身规律,进而去优化匹配的效率. 例如字符串“ababcb”,明显看出是ab出现一组重复,若出现如下匹配模式:. 此时发生错误,一般情况下会选择移动Pattern一个位置来继续,事实证明效果不佳.

字符串匹配(BF,BM,Sunday,KMP算法解析)

- - CSDN博客综合推荐文章
字符串匹配一直是计算机领域热门的研究问题之一,多种算法层出不穷. 字符串匹配算法有着很强的实用价值,应用于信息搜索,拼写检查,生物信息学等多个领域. 今天介绍几种比较有名的算法:. BF(Brute Force)算法又称为暴力匹配算法,是普通模式匹配算法. 其算法思想很简单,从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则主串和模式串都后移一个字符继续比较;若不相同,则回溯到主串S的第pos+1个字符重新开始比较.

转载一篇单字符串匹配KMP算法最好理解的文章

- - 编程语言 - ITeye博客
字符串匹配是计算机的基本任务之一.   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD".   许多算法可以完成这个任务,. Knuth-Morris-Pratt算法(简称KMP)是最常用的之一.

KMP、AC自动机在字符串匹配类动态规划问题中的应用

- Sosi - C++博客-Mato is No.1
有一类动态规划(其中也包含递推)问题,要求满足一些限制条件的字符串,这些限制条件是“需要含有某个子串”或“不能含有某个子串”,那么KMP、AC自动机等就有大用了. 题意:字符集中有一些字符,给出每个字符的出现概率(它们的和保证为1),再给出一个子串B,求:任给一个长度为N的字符串A(只能包含字符集中的字符),使得S是A的子串的概率.

字符串匹配那些事(一)

- jiessie - 搜索技术博客-淘宝
本系列文章主要介绍几种常用的字符串比较算法,包括但不限于蛮力匹配算法,KMP算法,BM算法,Horspool算法,Sunday算法,fastsearch算法,KR算法等等. 本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法. 所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右.

字符串匹配的Boyer-Moore算法

- - 阮一峰的网络日志
上一篇文章,我介绍了 KMP算法. 但是,它并不是效率最高的算法,实际采用并不多. 各种文本编辑器的"查找"功能(Ctrl+F),大多采用 Boyer-Moore算法. Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解. 1977年,德克萨斯大学的Robert S.

最佳字符串匹配算法(Damerau-Levenshtein距离算法)的Java实现

- - Java - 编程语言 - ITeye博客
原文: http://www.javacodegeeks.com/2013/11/java-implementation-of-optimal-string-alignment.html.  It implements a few well known tricks to use less memory by only hanging on to two arrays instead of allocating a huge n x m table for the memoisation table.

JavaScript中的字符串操作

- - CSDN博客推荐文章
JavaScript中的字符串操作.    字符串在JavaScript中几乎无处不在,在你处理用户的输入数据的时候,在读取或设置DOM对象的属性时,在操作cookie时,当然还有更多.... JavaScript的核心部分提供了一组属性和方法用于通用的字符串操作,如分割字符串,改变字符串的大小写,操作子字符串等.