★ 第三十九讲 KMP算法之实现及优化 |【KMP系列核心】★

小牧羊

小牧羊

#include <stdio.h>
typedef char* String;

void get_next( String T, int *next )
{
        int j = 0;
        int i = 1;
        next[1] = 0;

        while( i < T[0] )
        {
                if( 0 == j || T[i] == T[j] )
                {
                        i++;
                        j++;
                        if( T[i] != T[j] )
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若不存在，则返回0
int Index_KMP( String S, String T, int pos )
{
        int i = pos;
        int j = 1;
        int next[255];

        get_next( T, next );
        
        while( i <= S[0] && j <= T[0] )
        {
//增加判断，防止特殊情况发生
                if( 0 == j || S[i] == T[j] )
                {
                        i++;
                        j++;
                }
                else
                {
                        j = next[j];
                }
        }

        if( j > T[0] )
        {
                return i - T[0];
        }
        else
        {
                return 0;
        }
}
int main()
{
        char str[255]="ababaaaba";
        int next[255];
        int i=1;
        str[0]=9;
        get_next(str,next);
        printf("next数组的取值:\n");
        for(i=1;i<10;i++)
        {
                printf("%3d",next[i]);
        }
    putchar('\n');
}

小牧羊

这样的结果，很尴尬

圣狄雅哥

小牧羊 发表于 2017-12-9 10:23
这样的结果，很尴尬

输入的字符串前面要有一个空格，它作为str [0]存放字符串长度。

圣狄雅哥

小牧羊 发表于 2017-12-9 10:23
这样的结果，很尴尬

输出正确的next数组为：0 1 0 1 0 4 2 1 0

圣狄雅哥

……
int i = pos;
        int j = 1;
        int next[255];

        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数组的