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