有这么一个神奇的算法

{% blockquote 百度百科 http://baike.baidu.com/link?url=wb7ZQzyJipCv5V0f5czncXfPJgv8oz3-dYV4iPnqYATD3tXfzn5cSVD5t3XJTbXMXNGGeI_GnVVzkcgFUa8_Ha KMP算法%}
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
{% endblockquote %}

字符串匹配算法，要求我们对于两个字符串a,b。
找出字符串b在字符串a中第一次出现的位置。

例如在ABCABCABCDABC中寻找ABCABCD
按照较为暴力的搜索方法，当我们搜索到

发现最后一个不匹配，则我们应该改变起始位置，从头开始匹配

显然，这样改变效率极为低下。
因为当我们能够匹配到D，证明字符串前面一定是ABCABC
因此，应该充分利用已经匹配过的部分，从而更快速地匹配。

这个神奇的算法叫做KMP算法

对字符串b进行分析：
假如我们匹配到D，字符串a一定有ABCABCX，这时，我们只需要从上一个ABC处继续匹配即可。
即：

而这样做的原理是什么呢?

对于已经确定的ABCABC,需要找的应该是：
尽可能找到一个最长的字符串满足从头开始到一个位置与从一个位置到最后匹配的地方相同

或者换种描述方式：
尽可能少地舍弃已匹配字符串后面的部分，使剩下未舍弃的部分能够与已知部分后部相同

• 之所以要尽可能少舍弃已匹配部分，是因为匹配字符串是从前向后匹配的，因此字符串b前面部分必须是留下的；
• 之所以让剩下未舍弃的部分能够与已知部分后部相同，是因为下一位不匹配，匹配点应该后移，因此字符串b需要往后移，最后字符串a留下的是已匹配部分后面部分

可以发现，不管是字符串a已匹配部分的后半部分还是字符串b的前半部分，其实都应该在字符串b已匹配部分中。

也就是说，我们只需要找到字符串b已匹配部分中，从前往后一个一个加字符的所有字符串(前缀字符串)和从后往前一个一个加字符串的所有字符串(后缀字符串)即可

对ABCABC
其有前缀字符串：

• A
• AB
• ABC
• ABCA
• ABCAB

有后缀字符串：

• C
• BC
• ABC
• CABC
• BCABC

可以看出，其前缀字符串和后缀字符串最长的匹配是ABC,长度为3

也就是说，当我们匹配到D发现不匹配时，我们保持在字符串a中的位置i不变，在字符串b中的位置j向前移动3个距离

由于匹配到j时，我们要找的最长匹配其实是到这个位置上一个位置的最长匹配，因此将字符串b中所有的最长匹配按照位置依次后移一位就是next数组

字符串b中的第一个字符没有前一个字符，因此应该特殊处理(如果到这里都没有匹配到，那么就意味着需要从0开始匹配，没有已匹配部分了)，可以将其记为-1

我只想知道怎么应付考试

next数组的含义

到该位置上一个位置字符串的前缀字符串和后缀字符串最大的匹配数
如果每次都这样计算，显然计算量会非常大。

因此，可以采取其他方法计算next数组。

由于前缀字符串的第一个字符是确定的(总是字符串b的第一个字符)
后缀字符串的最后一个字符也总是确定的(总是已匹配部分最后一个字符)

采用递推的思想，当我们计算next[j]时，next[j-1]必定是计算好的
并且，next[j-1]对应的必定是j-1位置的字符的最大匹配数。
如果在字符串中加上j位置的字符，相当于改变了后缀字符串的最后一个字符。
如果要找新的字符串的最大匹配，只需要看旧的字符串最大匹配位置的下一个位置是不是和新的字符相同
如果相同，那么必然直接将上一个最大匹配+1即可
如果不相同，就找更短的那个匹配，查看它下一个位置的字符是否相同。

举个例子：

对于char b[]=ABCABCD有：

1. j=0，记录next[0]=-1
2. j=1，记录next[1]=0
3. j=2，查看b[next[2-1]](A)与b[2-1](B)。
   不相同，查看b[next[next[2-1]]](无意义)。记录next[2]=0
4. j=3，查看b[next[3-1]](A)与b[3-1](C)。
   不相同，查看b[next[next[3-1]]](无意义)。记录next[3]=0
5. j=4，查看b[next[4-1]](A)与b[4-1](A)。
   相同，记录next[4]=next[next[4-1]]+1(1)
6. j=5，查看b[next[5-1]](B)与b[5-1](B)。
   相同，记录next[5]=next[next[5-1]]+1(2)
7. j=6，查看b[next[6-1]](C)与b[6-1](C)。
   相同，记录next[6]=next[next[6-1]]+1(3)
8. j=7，查看b[next[7-1]](A)与b[7-1](C)。
   相同，记录next[7]=next[next[7-1]]+1(4)
9. j=8，查看b[next[8-1]](B)与b[8-1](C)。
   相同，记录next[8]=next[next[8-1]]+1(5)
10. j=9，查看b[next[9-1]](C)与b[9-1](C)。
    相同，记录next[9]=next[next[9-1]]+1(6)
11. 如果还有j=10(b[10]=E)，查看b[next[10-1]](A)与b[10-1](D)。
    不相同，查看b[next[next[10-1]]](A)
    不相同，查看b[next[next[next[10-1]]]](A)
    不相同，查看b[next[next[next[next[10-1]]]]](无意义)。记录next[10]=0

也即

按照学校的数据结构教材上，需要把next数组所有数加上1(从1开始的字符串)

代码实现

待补充