串模式匹配的KMP算法的next[]算法怎么理解
书上是这样写的
void get_next(SString T,int next[])
{
int i=1;
next[1]=0;
int j=0;
while(i<T[0])
{
if(j==0 || T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
希望能给出点详细的解释，望各位大神们不吝赐教啊
[解决办法]
T[0]里存的是长度, 字符串实际存放在T[1,...,n]中。依次计算next[i]的值
假设已经计算了next[i]=j-1,这表示i的位置之前（不包括i）的j-1个字符和字符串开始的j-1个字符是匹配的，并且这个j是最大的。可以根据这个算next[i+1]的值：
1. 如果T[i]==T[j]，表示继i之后继续匹配，那么next[i]=j; 显然这已是最大的
2. 否则，令j=next[j],（最难理解的地方！表示当前所能匹配的最长长度），回到1，直到1满足
