首页 > 代码库 > KMP

KMP

1.怎么来的

技术分享

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

所以要做的就是分析将要被匹配的字符串,这里的是ABCDABD,这样完成下一次要向后移动的位数。

向后移动的位数为:

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

已经匹配的字符数:上面图片的已经匹配的字符是ABCDAB所以有6个已经匹配的字符数,这里最后一个匹配的字符是B,他的部分匹配值为2,所以后移4位成为

技术分享

 

2.介绍一下部分匹配表(Partial Match Table)

2.1前缀、后缀

技术分享

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

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

2.2产生部分匹配表

技术分享

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

2.3 部分匹配表的意义

技术分享

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

 

 

cankao阮一峰的日志

KMP