不理解kmp算法里的next函数的实现

下面是kmp算法的模式值next函数,大家能给我讲讲下面的程序实现吗,我实在是看不懂了!!!
#include<iostream.h>
void get_nextval(const char *T, int next[]) 
{ 
     // 求模式串T的next函数值并存入数组 next。
     int j = 0, k = -1; 
      next[0] = -1; 
      while ( T[j/*+1*/] != '\0' ) 
      { 
             if (k == -1 || T[j] == T[k]) 
             { 
                    ++j; ++k; 
                    if (T[j]!=T[k]) 
                           next[j] = k; 
                    else 
                           next[j] = next[k]; 
             }// if
            else 
                    k = next[k]; 
      }// while

}
int main()
{
char* T="ababcaabc";
int next[9];
get_nextval(T,next);
for(int i=0;i<9;i++)
cout<<next[i]<<endl;
return 0;
}

1 个解决方案

#1

 ababcaabc // 初始化
A^
B^
 0
 ababcaabc // 1
A ^
B^
 00
 ababcaabc // 2
A  ^
B^
 000
 ababcaabc // 3
A   ^
B ^
 0000
 ababcaabc // 4
A    ^
B  ^
 00002
 ababcaabc // 5
A     ^
B^
 000020
 ababcaabc // 6
A      ^
B ^
 0000201
 ababcaabc // 7
A       ^
B ^
 00002010
 ababcaabc // 8
A        ^
B  ^
 000020102

循环直到A到达字符串结尾 {
	A++
	如果AB字符相同 {
		// 第2,3,5,7步.
		A的NEXT <- B的NEXT.
		B++
	} 否则 {
		// 第1,4,6,8步
		A的NEXT <- B的值.
		循环: B <- B的NEXT,直到B位置为0或AB字符相同.
		如果AB字符相同 {
			// 第6步
			B++
		}
	}
}

只能这么帮你了,自己看吧,应该不难.不过我给的东西是优化过的,KMP本身并没有"否则中的B回退的"步骤.
你给的那个算法可能是把B回退的步骤和最外面的循环合并了(很多书上都是如此),导致代码很难读..