在大学的时候，应该在资料结构里面都看过 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 }