在大學的時候，應該在資料結構裏面都看過 kmp 演算法吧，不知道有多少老師對該演算法是一筆帶過的，至少我們以前是的，
確實 kmp 演算法還是有點饒人的，如果説紅黑樹是變態級的，那麼 kmp 演算法比紅黑樹還要變態，很抱歉，每次打 kmp 的時候，輸
入法總是提示 “看毛片” 三個字, 嘿嘿，就叫 “看毛片演算法” 吧。
一：BF 演算法
如果讓你寫字串的模式匹配，你可能會很快的寫出樸素的 bf 演算法，至少問題是解決了，我想大家很清楚的知道它的時間復
雜度為 O（MN），原因很簡單，主串和模式串失配的時候，我們總是將模式串的第一位與主串的下一個字元進行比較，所以複雜
度高在主串每次失配的時候都要回溯，圖我就省略了。
二：KMP 演算法
剛才我們也説了，主串每次都要回溯，從而提高了時間複雜度，那麼能不能在 “主串” 和 “模式串” 失配的情況下，主串不回溯呢？
而是讓” 模式串 “向右滑動一定的距離，對上號後繼續進行下一輪的匹配，從而做到時間複雜度為 O（M+N）呢？所以 kmp 演算法就是
用來處理這件事情的，下面我們看下簡單的例子。
通過這張圖，我們來討論下它的一般推理，假設主串為 S，模式串為 P，在 Si != Pj 的時候，我們可以看到滿足如下關係式 57 ///
58 /// 文章來自互聯網博客網站。原文地址：http://www.cnblogs.com/huangxincheng/archive/2012/12/01/2796993.html
Si-jSi-j+1…Sn-1=P0P1..Pj-1 。那麼模式 P 應該向右滑動多少距離？也就是主串中的第 i 個字元應與模式串中的哪一個字元進行比較？
假設應該與模式串中的第 k 的位置相比較，假如模式串中存在最大的字首真子串和字尾真子串，那麼有 P0P1..Pk-1=Pj-kPj-k+1…Pj-1.
這句話的意思也就是説，在模式 P 中，前 k 個字元與 j 個字元之前的 k 個字元相同，比如説：“abad” 的最大字首真子串為 “aba”，最大
字尾真子串為 “bad”，當然這裏是不相等，這裏的 0
55 /// pj-k,pj-k+1….pj-1（字尾串)
56 ///
59 static int[] GetNextVal(string smallstr)
60 {
61 //字首串起始位置 (“-1″ 是方便計算）
62 int k = -1;
63
64 //字尾串起始位置（”-1″ 是方便計算）
65 int j = 0;
66
67 int[] next = new int[smallstr.Length];
68
69 //根據公式： j=0 時，next[j]=-1
70 next[j] = -1;
71
72 while (j < smallstr.Length - 1)
73 {
74 if (k == -1 || smallstr[k] == smallstr[j])
75 {
76 //pk=pj的情況: next[j+1]=k+1 => next[j+1]=next[j]+1
77 next[++j] = ++k;
78 }
79 else
80 {
81 //pk != pj 的情況: 我們遞推 k=next[k];
82 //要麼找到，要麼 k=-1 中止
83 k = next[k];
84 }
85 }
86
87 return next;
88 }
89 }
90 }