1.在KMP字符串匹配算法中，我们需要先求出next数组，由于过程比较抽象，现在一步一步来讲解。
2.next数组的求法：首先next[0]=0，next[1]=1，这个是基础。假设字符串为str，当前位为i，则判断str[i-1]是否等于i-1上对应的next值对应的内容，即str[next[i-1]-1]，为什么还需要把next的值减1？因为next数组的计算，是把字符串按照1，2，3，4。。。。从1开始的规则来计算的。
如果str[i-1]==str[next[i-1]-1]，那么next[i]=next[i-1]+1；
如果不等，我们令j=next[i-1]，判断str[i-1]是否等于str[next[j-1]-1]，如果不等于，我们令j=next[j-1]，继续判断str[i-1]是否等于str[next[j-1]-1]，一直循环判断，直到相等，则next[i]=next[j-1]+1。
我们来看看数组
KMP序号: 1 2 3 4 5 6 7 8 9 10 11 12
string： a b a b a a a b a b a a
next数组：0 1 1 2 3 4 2 2 3 4 5 6
数组idx： 0 1 2 3 4 5 6 7 8 9 10 11
我们从第三位开始分析，
注意下面涉及到的str[i]，是按照正常的string获取位置，不是按照KMP序号，即str为str[0,1,2,3…..10,11]，next为next[0,1,2,3…..10,11]。
第三位i=2：前一位str[1]=’b’，next[1]=1，str[next[1]-1]=’a’，’b’!=’a’，所以再往前一步已经无字符，所以next[2]=1;
第四位i=3：前一位str[2]=’a’，next[2]=1，str[next[2]-1]=’a’，相等，所以next[3]=next[2]+1=2;
第五位i=4：前一位str[3]=’b’，next[3]=2，str[next[3]-1]=str[1]=’b’，相等，所以next[4]=next[3]+1=3;
第六位i=5：前一位str[4]=’a’，next[4]=3，str[next[4]-1]=str[2]=’a’，相等，所以
next[5]=next[4]+1=4;
第七位i=6：前一位str[5]=’a’，next[5]=4，str[next[5]-1]=str[3]=’b’，与str[5]不相等，所以继续看前一个next，即next[next[5]-1]=next[3]，str[next[3]-1]=str[1]=’b’，依然不相等，继续往前看next[next[3]-1]=next[1]，str[next[1]-1]=str[0]=’a’，相等，则next[6]=next[1]+1=2;
第八位i=7：前一位str[6]=’a’，next[6]=2，str[next[6]-1]=str[1]=’b’，与str[6]不相等，所以继续看前一个next，即next[next[6]-1]=next[1]，str[next[1]-1]=’a’，与str[6]相等，所以next[7]=next[1]+1=2;
第九位i=8：前一位str[7]=’b’，next[7]=2，str[next[7]-1]=str[1]=’b’，与str[7]相等，所以next[8]=next[7]+1=3;
第十位i=9：前一位str[8]=’a’，next[8]=3，str[next[8]-1]=str[2]=’a’，与str[8]相等，所以next[9]=next[8]+1=4;
第十一位i=10：前一位str[9]=’b’，next[9]=4，str[next[9]-1]=str[3]=’b’，与str[9]相等，所以next[10]=next[9]+1=5;
第十二位i=11：前一位str[10]=’a’，next[10]=5，str[next[10]-1]=str[4]=’a’，与str[10]相等，所以next[11]=next[10]+1=6;
至此，next数组求取完毕。
初步代码如下：
[c language=”++”]
next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
if (str[i – 1] == str[next[i – 1] – 1])
next[i] = next[i – 1] + 1;
else
{
int j = next[i – 1];
while (j>0 && str[i – 1] != str[j – 1])
{
j = next[j – 1];
}
next[i] = next[j] + 1;
}
}
[/c]
优化后的代码如下：
[c language=”++”]
next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
int j = i;
while (j>1 && str[i – 1] != str[next[j – 1] – 1])
j = next[j – 1];
next[i] = next[j – 1] + 1;
}
[/c]