string 之 strchr函數 和 strstr函數（BF算法和KMP算法的應用）

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函數修正值的算法如下，此時比對算法不變。

綜合以上，彙總一下代碼，全部代碼已經嚴格測試通過。

歡迎指正交流！