对于next[]数组 也就是子串的某个位置与自身的公共前缀的最后匹配位置。 这样讲可能有点抽象，说白了就是子串以该位置为最末位，自己和自己匹配的最长公共前缀。 而在进行next[]数组的第i个位置的求值时，该位置以前的所有next[]值已经求出，因此我们可以借助之前求出的next[]值来更新此刻next[i]的值。 所以时间复杂度为O(2*m) 拿ababac来说： 第一步： ababac _ababac i,j在一开始就失配，即next[2]=0。

第二步： ababac __ababac i,j在第3位匹配，next[3]=1 同理：next[4]=2,next[5]=3,next[6]=4 在i=6,j=4时失配。 因此，将j=next[j]+1,i++，也就是匹配串后移。 即： ababac ______ababac 此时，两串失配，next[7]=0 求next[]数组代码： int next[100]; char str2[100]; void get_next() { int len2=strlen(str2); int i=1,j=0; while(i