Author: bakari Date: 2012/8/9
继上篇。。。。。
下面是我写的代码与源码作的一些比较,均已严格测试通过,分别以“string 之”系列述之。
strchr函数:求字符在字符串中所在的位置
strstr函数:求子串在主串中的起始位置(用的字符串的模式匹配算法)
下面着重讲解BF算法和KMP算法,要真正懂一个算法并将它吃透,一定要懂这个算法的历史,回到最初去了解这个算法是怎样被发现的。对于相对感性的东西不用追本溯源,咬文嚼字,但是对于理性(换个词叫抽象)的东西一定不能急躁,即使短时间内能够清楚了解之,但过了一阵之后毫无疑问会忘记,本人上学期上DS的时候已经学过这个算法,当时就是为了坑爹的考试,没有好好吃透,导致现在需要又要重新去复习回味。所以,为了做个高效的人士,还是那句老话,欲速则不达,好的算法就应该慢下心来慢慢品味,从它的根抓起。将之吃透!
本文是不会跟你去讲历史的,So,想知道历史的就Google,百度吧,在下也帮不了,本文只做简单的总结,加深印象。
一 、BF算法
这个算法符合人的思维过程,不用转弯,一看便知.为了显示清晰,用途代替文字
看着图就可以写代码了:
缺点:低效,复杂度O(M*N)
但在某些场合,如文本编辑啊,效率也较高,但对于计算机的二进制文件就显得苍白无力。
二、KMP算法
所以这个时候KMP算法诞生了,由于是三个人提出了的,所以用了三个人的名字的开头字母作为名称,我只记得Knuth,这个人实在太有名了,计算机科学的鼻祖,计算机所有奖项都拿过。
KMP算法是对BF算法的改进,当匹配失效是指针不回溯,根据失效函数(即Next[n]的值)进行下一轮的匹配。
E.g: 主串 “a b a b c a b c a c b a b” 模式串 “a b c a c”
第一趟匹配: a b a b c a b c a c b a b i = 2 i 不回溯
a b c j = 2
第二趟匹配: a b a b c a b c a c b a b i= 6
a b c a c j = 4
第三趟匹配:a b a b c a b c a c b a b i= 10
a b c a c j = 5
依上所得:用数学的语言表述:
假设主串:S1S2.....Sn 模式串:P1P2......Pm
当主串中第 i 个字符与模式串第 k 个字符不匹配,前提是前面的字符皆已匹配,则有下面的关系:
P1P2......P(k-1) = S(i - k + 1)S(i - k + 2)......S(i - 1); ...................................(1)
而对于模式串,有如下关系:
P(j - k + 1)P(j - k + 2)......P(j - 1) = S(i - k + 1)S(i - k + 2)......S(i - 1);..........(2)
根据(1)(2),得:
P1P2......P(k-1) = P(j - k + 1)P(j - k + 2)......P(j - 1);
即最终只需要在模式串中进行比较,这个比较就是计算Next[j]的值,用此作为模式串的指针回溯点。下面会介绍到。
根据以上的推导就可以宏观地写出KMP的算法的实现:
所以,这个算法最终化为小问题,即求Next[j] 的值。
对于Next[j]的数学推导:
令Next[j] = k,则Next[j] 表明当模式中第 j 个字符与主串 中相应字符失效时,在模式中需重新和主串中该字符进行比较的字符的位置,由此可引出Next[j]函数的定义:
Next[j] = -1 , 当 j = 1时;
= Max{k | 1 < k < j && P1P2......P(k - 1) = P(j - k + 1)......P(j - 1) }
= 0 其他情况;
E.g: j : 0 1 2 3 4 5 6 7
模式串: a b a a b c a c
Next[j]: -1 0 0 1 1 2 0 1 0
很好计算,关键是不单要知其为,更要知其所以为。所以理解本质很重要。
下面,看一个例子就懂了:
假设:主串: “a c a b a a b a a b c a c a a b c” 模式串:“a b a a b c a c”
第一趟:a c a b a a b a a b c a c a a b c i = 1;
a b j = 1; Next[j] = 0;
第二趟:a c a b a a b a a b c a c a a b c i = 1;
a j = 0; Next[j] = -1 //模式串中的第一个元素不想等,i 后移;
第三趟:a c a b a a b a a b c a c a a b c i = 7
a b a a b c j = 5; Next[j] = 2;
第四趟:a c a b a a b a a b c a c a a b c i = 13;
a b a a b c a c j = 8; END!
了解到这里,就很容易写出一份很好的代码了:
Note:还未完,下面的很重要
前面定义的Next[]函数在某些情况下有缺陷。E.g:模式串“aaaab”在和主串“aaabaaaab”匹配时,当i = 3, j = 3 时,不等,但由Next[j]的指示还需进行 i = 3, j = 2 ; i = 3, j = 1; i = 3, j = 0这三次的比较,实际上,因为模式串中第1,2,3个字符和第四个字符都相等,因此不需要再和主串第4个字符相比较,而可以直接将模式串一气像右滑动4个字符。这就是说,若按上述定义得到的Next[j] = k,而模式串中Pj = Pk ,则当主串中字符Si 和 Pj 比较不等时,不需要再和Pk进行比较,而直接和P(Next[k]) 进行比较,有点绕啊,那就 看一个实例吧:
E.g: j : 0 1 2 3 4
模式串: a a a a b
Next[j]: -1 0 1 2 3 0
Next2[j]: -1 0 0 0 3 0
换句话说就是:此时的Next[j] 应该和Next[k] 相同。由此可计算Next函数修正值的算法如下,此时匹配算法不变。
综合以上,汇总一下代码,全部代码已经严格测试通过。
欢迎指正交流!