http://blog.csdn.net/l953972252/article/details/51331001
字符串匹配一直是计算机领域热门的研究问题之一,多种算法层出不穷。字符串匹配算法有着很强的实用价值,应用于信息搜索,拼写检查,生物信息学等多个领域。
今天介绍几种比较有名的算法:
1. BF
2. BM
3. Sunday
4. KMP
—,BF算法
BF(Brute Force)算法又称为暴力匹配算法,是普通模式匹配算法。
其算法思想很简单,从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则主串和模式串都后移一个字符继续比较;若不相同,则回溯到主串S的第pos+1个字符重新开始比较。
依次类推,直到模式串T中每个字符依次和主串S中的一个连续字符串全部相等时,则匹配成功,返回模式串T的第一个字符在主串S中的位置;若主串遍历完也没有成功,则匹配失败。
算法步骤如下:
- 1
- 2
- 3
- 1
- 2
- 3
第一次比较,从左到右,S[0] = T[0],计数器++;比较S[1] = T[1],i++;当s[2] != T[2],主串回溯,从S[1]重新开始比较。
- 1
- 2
- 3
- 1
- 2
- 3
也就是说,主串i从0开始,每次比较失败i++,重新比较,直到
- 1
- 2
- 3
- 1
- 2
- 3
i = 5,匹配成功。返回 i=5。
可推得,BF算法在最坏情况下需要比较,主串长度M 乘以 模式串长度N, 为-O(M * N)。
代码实现如下:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
BF算法简单易懂,但是这个算法效率很差,原因在于每次失败后回溯,浪费了之前的比较,导致了很多次的无用比较,时间损耗较大。
二,BM算法
BM(Boyer Moore)算法是1977年,Robert S.Boyer和J Strother Moore提出了一种在O(n)时间复杂度的匹配算法。时间复杂度要低于BF。
BM算法之所以能够在模式匹配中有更高的的效率,主要是因为BM算法构造了两个跳转表,分别叫做 坏后缀表 ,和 好后缀表 。这两个表涉及了BM算法中的两个规则:
坏字符规则:当文本串中的某个字符跟模式串的某个字符不匹配时,我们称文本串中的这个失配字符为坏字符,此时模式串需要向右移动,移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外,如果”坏字符”不包含在模式串之中,则最右出现位置为-1。
好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。
算法步骤如下:
1. 首先,”文本串”与”模式串”头部对齐,从尾部开始比较。”S”与”E”不匹配。这时,”S”就被称为”坏字符”(bad character),即不匹配的字符,它对应着模式串的第6位。且”S”不包含在模式串”EXAMPLE”之中(相当于最右出现位置是-1),这意味着可以把模式串后移6-(-1)=7位,从而直接移到”S”的后一位。
2. 依然从尾部开始比较,发现”P”与”E”不匹配,所以”P”是”坏字符”。但是,”P”包含在模式串”EXAMPLE”之中。因为“P”这个“坏字符”对应着模式串的第6位(从0开始编号),且在模式串中的最右出现位置为4,所以,将模式串后移6-4=2位,两个”P”对齐。
3. 依次比较,得到 “MPLE”匹配,称为”好后缀”(good suffix),即所有尾部匹配的字符串。注意,”MPLE”、”PLE”、”LE”、”E”都是好后缀。
4. 发现“I”与“A”不匹配:“I”是坏字符。如果是根据坏字符规则,此时模式串应该后移2-(-1)=3位。问题是,有没有更优的移法?
5. 更优的移法是利用好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。
所有的“好后缀”(MPLE、PLE、LE、E)之中,只有“E”在“EXAMPLE”的头部出现,所以后移6-0=6位。
可以看出,“坏字符规则”只能移3位,“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数,只与模式串有关,与原文本串无关。
6. 继续从尾部开始比较,“P”与“E”不匹配,因此“P”是“坏字符”,根据“坏字符规则”,后移 6 - 4 = 2位。因为是最后一位就失配,尚未获得好后缀。
匹配完成,可见BM算法根据好坏字符规则,使得失配时,文本串能够后移更多位,使得效率高于BF按部就班的匹配。
BM算法的时间复杂度为-O(N)。
代码实现主要在于构建两表。
坏字符表:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
好后缀表:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
构建完表BM算法就很简单了。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
BM算法的思想在字符串匹配中很重要,其中好后缀与KMP算法的思想不谋而合,而坏字符跳跃,跟Sunday算法很相似。总的来说,BM是很高效的匹配算法。
三,Sunday算法
Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。据网上说,Sunda算法的效率高于BM和KMP(不太明白)。在我看来,Sunday算法是BM算法的优化,逻辑简单易懂,代码也实现更容易(无需构造两表)。
Sunday算法的思想是:
1. 从文本串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则主串和模式串都后移一个字符继续比较;
2. 若不相同,则将文本串参与匹配的最末位字符的后一个字符与模式串逆着匹配。
3. 若匹配完模式串没有该字符,则模式串直接跳过,即移动位数 = 匹配串长度 + 1。
4. 若模式串匹配到了该字符,则模式串中相同字符移动到文本串该字符下,与该字符对齐。其移动位数 = 模式串中最右端的该字符到末尾的距离+1。
算法步骤如下:
- 1
- 2
- 3
- 1
- 2
- 3
从前往后比较,在i = 2处失配,关注i= 4( d )是否包含在模式串T中。遍历比较完发现不包含,将模式T移动到i = 5继续比较。(失配后,主串这轮参与比较的后一位(d)肯定要参与下一轮的比较,T中都没有d,肯定匹配不成功啊!还比什么,直接后移至(d)的下一位。)
- 1
- 2
- 3
- 1
- 2
- 3
在i = 7处失配,关注i = 9(b),在模式串中找b,发现i = 6, i = 7处都有b,那应该和谁对齐?? 应该和后面的(i = 7)处的对齐,这就是为什么要倒着在模式串中找b了,找到了直接break,并将此处与i = 9对齐。(为什么和后面的b对齐,大家思考)
- 1
- 2
- 3
- 1
- 2
- 3
在i=7处失配,关注i=11(a),匹配到模式串中最后一位为a,break;将模式串中的a与i = 17 处的 a 对齐。继续比较。
- 1
- 2
- 3
- 1
- 2
- 3
匹配完成!
可见Sunday算法的核心思想就是失配时,模式串能尽可能多的向后移动,使得匹配次数减少,效率提高。
Sunday和BM不同点在于:
1. BM从后往前匹配,Sunday从前往后。
2. BM算法失配关注的是“最后一位”,Sunday关注的是“最后一位的下一位”。
3. BM有坏字符串好字符串之分,Sunday没有。(但思想比较相似,BM中的好字符 和 坏字符包含在模式串内,可以类比于Sunday算法找到了该字符;好字符和坏字符串没出现,则类比于没在模式串中找到该字符)。
代码实现:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
Sunday算法的应用价值很强,(实际效率高于KMP和BM算法),代码实现也很简单,希望大家能够掌握。
四,KMP算法
Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
KMP算法在网上说的非常麻烦,我觉得就是之前介绍的类似于BM算法的好字符后缀匹配规则,和next[]数组的推导两点而已。
算法的思想是:假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置如果j = -1(标记),或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。意味失配时,模式串P相对于文本串S向右移动了j - next [j] 位。换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值。即移动的实际位数为:j - next[j],且此值大于等于1。
Next数组的值含义是:代表失配前的字符串中,有多大长度的相同的前缀后缀。比如Next[j] = k;表示 j 之前的字符串中有最大长度为k 的相同前缀后缀。
此也意味着在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到j-Next[j]这个位置上。所以重点在于求Next[]。
如下:
ABCDAB ABCDABC ABCDABCDABDABD 文本串
ABCDABD 模式串
最大前缀后缀相同数:
A 左 右
AB A B 0
ABC A,AB C,BC 0
ABCD A,AB,ABC D,CD,BCD 0
ABCDA A,AB,ABC,ABCD A,DA,CDA,BCDA 1
ABCDAB A,AB,ABC,ABCD,ABCDA B,AB,DAB,CDAB,BCDAB 2
ABCDABD A,AB,ABC,ABCD,ABCDA,ABCDAB D,BD,ABD,DABD,CDABD,BCDABD 0
最大前缀后缀公共元素长度对照表
A B C D A B D
0 0 0 0 1 2 0
Next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过上步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第求得的值整体右移一位,然后初值赋为-1,如下表格所示:
A B C D A B D
-1 0 0 0 0 1 2
在匹配失配时,只需要用失配位置 j 减去 Next[j],就可以得到模式串移动到什么位置了。
Next[]的求取代码实现如下:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
这段代码是为了求取Next[]对应的值,并没有什么实际意思,能得出正确的Next[]就行(求Next[]的值,网上好像就这一种代码实现办法)。
- 1
- 2
- 1
- 2
我们来根据代码验证下是否准确
str_len - 1~6
left = -1
right = 0
——————————————
0 1 2 3 4 5 6
next -1 0
left = 0
right = 1
next[1] = 0
--------------------------------------------
ABCDABD
right = 1
left = next[0] = -1
--------------------------------------------
left = 0
right = 2
next[2] = 0
0 1 2 3 4 5 6
next -1 0 0
可以看出是正确的(后来的就不用推演了),代码设计的很巧妙,能恰好算出Next[]所对应的值。(这段代码不需理解,记住就行,就是为了求Next[]而专门设计的算法)。
求出Next[]的对应值,KMP算法代码就很容易了。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
KMP的时间复杂度:
我们发现如果某个字符匹配成功,模式串首字符的位置保持不动,仅仅是i++、j++;如果匹配失配,i 不变(即 i 不回溯),模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功,算法结束。
所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为-O(n),算上计算next的-O(m)时间,KMP的整体时间复杂度为-O(m + n)。
四种经典的字符串匹配算法介绍完毕,大家在纸上多画多算,能更好的理解算法思想。