typedef char* String;
void get_next( String T, int *next )
{
int j = 0;
int i = 1;
next = 0;
while( i < T )
{
if( 0 == j || T == T )
{
i++;
j++;
if( T != T )
{
next = j;
}
else
{
next = next;
}
}
else
{
j = next;
}
}
}
// 返回子串T在主串S第pos个字符之后的位置
// 若不存在，则返回0
int Index_KMP( String S, String T, int pos )
{
int i = pos;
int j = 1;
int next;
get_next( T, next );
while( i <= S && j <= T )
{
//增加判断，防止特殊情况发生
if( 0 == j || S == T )
{
i++;
j++;
}
else
{
j = next;
}
}
if( j > T )
{
return i - T;
}
else
{
return 0;
}
}
int main()
{
char str="ababaaaba";
int next;
int i=1;
str=9;
get_next(str,next);
printf("next数组的取值:\n");
for(i=1;i<10;i++)
{
printf("%3d",next);
}
putchar('\n');
} 这样的结果，很尴尬 小牧羊 发表于 2017-12-9 10:23
这样的结果，很尴尬
输入的字符串前面要有一个空格，它作为str 存放字符串长度。 小牧羊 发表于 2017-12-9 10:23
这样的结果，很尴尬
输出正确的next数组为：0 1 0 1 0 4 2 1 0 ……
int i = pos;
int j = 1;
int next;
get_next( T, next );
……
index_kmp函数这里调用get _next函数，其i、j的值都会改变，为什么不影响后面的i、j呢？还是应该把调用get _next函数放在i、j赋值之前？还是调用的get _next函数中的i、j相对于index _kmp函数是局部变量不会影响主函数的i、j的值？ 圣狄雅哥 发表于 2018-2-28 16:01
……
int i = pos;
int j = 1;
查了一下资料，index_kmp函数中的i、j是局部变量，作用于整个index_kmp函数体内，虽然与被调函数get _next中的i、j同名，但作用域不同，不产生冲突；被调函数get _next中的i、j是只作用于该函数体内的局部变量，不会影响index _kmp函数中定义的i、j。 有KMP算法的源码吗？不是这个求next数组的
页:
[1]