KMP算法(向KMP致敬)

KMP算法用于在一个文本串S内查找一个模式串P出现的位置。
下面给出KMP算法的流程。假设现在文本串S匹配到i位置，模式串P匹配到j位置：
1)如果 j=-1,或者当前字符串匹配成功(即S[i] == P[j]),令i++,j++,匹配下一个字符;
2)如果j != -1且当前字符匹配失效(即S[i] != P[j])，则令i不动，j = next[j]。
此举意味着若匹配失败，模式串P相对于文本串S向右移动了j - next[j]位。
代码见:http://blog.csdn.net/helloworlddm/article/details/51933531
next数组中各个元素的值的含义:代表当前字符之前的字符串中，有多大长度的相同前缀和后缀。
寻找相同前缀和后缀的最大长度：对于P = P0P1...Pj-1Pj，寻找模式串P中长度最大且相等的前缀和后缀，如果存在"P0P1...Pk-1Pk" = "Pj-kPj-k+1...Pj-1Pj",那么在包含Pj的模式串中有最大长度为k+1的相同前缀和后缀。太抽象了，举个例子：
给定的模式串是"ABCDABD"

模式串中的各个子串	前缀	后缀	公共元素的最大长度
A	空	空	0
AB	A	B	0
ABC	A,AB	C,BC	0
ABCD	A,AB,ABC	D,CD,BCD	0
ABCDA	A,AB,ABC,ABCD	A,DA,CDA,BCDA	1
ABCDAB	A,AB,ABC,ABCD,ABCDA	B,AB,DAB,CDAB,BCDAB	2
ABCDABD	A,AB,ABC,ABCD,ABCDA,ABCDAB	D,BD,ABD,DABD,CDABD,BCDABD	0

寻找相同前缀和后缀的最大长度(abab为例)

模式串	a		b		a		b
相同前缀和后缀的最大长度	0		0		1		2
模式串	a	b		a		b
Next 数组	-1	0		0		1

观察可知next数组:将第二行求得的值整体右移一位，然后初值设为-1。
代码实现(含改进代码):http://blog.csdn.net/helloworlddm/article/details/51933531