转眼间，下个学期我们专业就要开《数据结构》这门课程了。想当初我自学数据结构的时候可谓是困难重重，现在我想到有可能我身边的同学们也会遇到和我一样的问题。于是我打算尽我的能力，把我在学习算法的过程中的一点感悟，或者是一些我自认为的难点，用我自己的话描述出来。希望可以给朋友们有所帮助。
我记得我遇到的第一个难题就是KMP算法。
KMP算法是一种改进的字符串匹配算法，由Knuth、Morris、Pratt三位前辈提出来的，取了这三个人的名字的头一个字母。KMP算法采用一种预处理，在不匹配发生的时候这个字符串自身包含足够的信息来确定下一个匹配将在哪里开始，以此避免对以前已匹配的字符的重新检查。
首先，我们简单介绍一下KMP算法的主要思路，然后小戴跟大家详细分析一下KMP中预处理待匹配串的过程。
这里我们举一个例子：假设主字符串Text = “abababababababc”，待查找字符串Pattern=” abababc”。我们用两个指针i和j分别表示Text[i – j + 1…i]与Pattern[1…j]匹配。也就是说，i是不断增长的，随着i的增长j相应的变化以达到Text[i]以前的j个字符与Pattern字符串开头的前j个字符相等。当然，j 越大越好了。现在开始匹配Text[i + 1]和Pattern[j + 1]，如果他们相等，那当然最好了，我们继续i++并且j++。如果不匹配的话，我们的策略是减少j的值使得Text[i – j + 1…i]与Pattern[1…j]相等且Text[i + 1]与Pattern[j + 1]也匹配。当j == Pattern串长度的时候，我们就说Pattern串是Text的子串。
我们来看一下KMP算法具体的处理过程：
i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T = a b a b a b a b a b a b a b c P = a b a b a b c j = 1 2 3 4 5 6 7
当i = j = 6时，Text[7] != Pattern[7]，那么我们就要减小j以使得串重新匹配。仔细观察一下我们发现，如果我们要避免重复比较之前已经匹配的字符串，我们需要找到一个最大的j，使得Pattern串的前j个字符与Text[6]之前的j个字符相等。而我们能匹配到这一步，就必定已经有Pattern[6]之前的字符与Text[6]之前的字符相等。换句话说，我们就是要找到一个最大的j，使得Pattern[1…6]的前j个字符与后j个字符相等。
在这里，Pattern[1…4] = “abab”，Pattern[3…6] = “abab”，于是，新的j = 4：
i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T = a b a b a b a b a b a b a b c P = a b a b a b c j = 1 2 3 4 5 6 7
以此类推，当匹配到i = 9, j = 7的时候，我们将会需要再一次地改变j。
在我们刚才的讨论中，j在每次失去匹配的时候需要作如何处理其实跟Text串无关，我们仅仅通过考虑Pattern串就能得出。这就是之前我们说的预处理，通过预处理我们可以得到一个数组，其实也就是严蔚敏老奶奶的《数据结构》里说的Next函数。当我们匹配到j，而j + 1不能继续匹配时，这时新的j应该是所有满足Pattern[1…next[j]] == Pattern[next[j]…j]的最大值。
下面是KMP算法的主过程：
void kmpMatch() {
int j = -1;
for(int i = 0; i < TEXT_LENGTH; i++) {
while(j > -1 && text[i] != pattern[j + 1]) {
j = next[j];
}
if(text[i] == pattern[j + 1]) {
j++;
}
if(j == (PATTERN_LENGTH - 1)) {
printf("Pattern occurs with shift %d\n", i - (PATTERN_LENGTH - 1));
j = next[j];
}
}
}
那么，如果快速而有效地进行这个预处理呢？我个人认为这是理解KMP算法的一大难点。几乎所有的资料或者教科书上都会说求得next数组的过程其实就是对Pattern串的一次自我匹配，然后说由于代码和KMP算法主过程代码类似，于是就一笔带过了。
可是很惭愧啊，我当时学习的时候偏偏就是不能理解这个过程。现在终于对它有一点儿明白了，在这里我把我的理解说出来。
我尽量给它阐述清楚，如有不对的地方欢迎大家拍砖。
-1 0 1 2 3 4 5 6 P = a b a b a b c next = -1 -1 0 1 2 3 -1
我们先来观察一下。为了下面表述方便，我们把Pattern串起始的0位的前一位，也就是我们标记出来的-1位显式地表示出来。
我们在这里仍然虚拟出两个指针i和j。其中i是持续增长的，用来遍历整个Pattern串，而j则标识当前Pattern[i – j + 1…i]与Pattern[1…j]能匹配的最长串。
我们从左边开始，当Pattern串连第一个元素”a”，即Pattern[0]，都不与Text串匹配时，我们别无它法，只能将整个Pattern串右移一位后再和Text串匹配，所以我们令next[0] = -1。此时j也应该被初始化为-1。
我们继续向前，检查Pattern[1] = b。因为它不等于第一个元素”a”，亦即Pattern[1] != Pattern[next[0] + 1]，所以要将j向后退，得到next[1] = -1。
到了Pattern[2] = a时，因为有Pattern[2] == Pattern[0]，于是j不用退，而是增加1。next[2] = 0。
同样，到了Pattern[3]时，由Pattern[3] == Pattern[1]，next[3] = 1。
以此类推，得到next[4] = 2，next[5] = 3。
好了，当我们考虑Pattern[6]时，我们发现Pattern[6] != Pattern[next[5] + 1]，再一次考虑j向后退。此时的j等于3。而前面已经算得next[3] = 1，于是我们令j倒退到1，即从next[5]倒退到next[3]。
然而Pattern[6]居然仍然不等于Pattern[j + 1]，我们只好把j继续向后退到next[j]即next[1]，这样一来j的值又变为-1。
很明显的，Pattern[6] != Pattern[next[1] + 1]。于是j不会再往后面退了，最终，我们得到next[6] = -1。
下面给出预处理过程的代码：
void getNext() {
int j = -1;
next[0] = -1;
for(int i = 1; i < PATTERN_LENGTH; i++) {
while(j > -1 && pattern[j + 1] != pattern[i]) {
j = next[j];
}
if(pattern[j + 1] == pattern[i]) {
j++;
}
next[i] = j;
}
}
KMP算法是一个很有研究价值的问题，它可以在线性时间内解决字符串的匹配，我听说正则表达式的解析器在解决字符串匹配的过程中也是用的KMP算法。
当然，我们解决字符串匹配还有很多其他的方法，比如自动机等。以后我们有可能会提到。
