首页 - 推荐新闻 - 大浪淘沙休闲会所,戎,彪马官网-实用列表新闻,每日整理,还原事实

大浪淘沙休闲会所,戎,彪马官网-实用列表新闻,每日整理,还原事实

发布时间:2019-07-12  分类:推荐新闻  作者:admin  浏览:294

作者:阮一峰
来历:http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

字符串匹配是计算机的根本使命之一。

举例来说,有一个字符串"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"的方位。

(完)

下一篇
快捷导航
最新发布
标签列表