wsx666946 发表于 2022-7-9 21:58:11

有关kmp算法问题

typedef struct
{       
        char data;
        int length;                        /
} SqString;

void GetNext(SqString t,int next[])               
{
        int j,k;
        j=0;k=-1;
        next=-1;//第一个字符前无字符串，给值-1
        while (j<t.length-1)
       
        {       
                if (k==-1 || t.data==t.data)         //k为-1或比较的字符相等时
                {       
                        j++;k++;
                        next=k;
                        //这里k比j小1是因为相等前后缀+1等于出现错误的位置对吧？
               }
               else
                {
                        k=next;//那这里为什么又用next的值赋给k了？这样不是一下少了两位么？
                       
                }
        }
}
int KMPIndex(SqString s,SqString t)//KMP算法
{

        int next,i=0,j=0;
        GetNext(t,next);
        while (i<s.length && j<t.length)
        {
                if (j==-1 || s.data==t.data)
                {
                        i++;j++;                       
                }
                else j=next;                 //这里是怎么运用next数组的也没有用函数调用 就是j=next; 怎么就把next数组用上了？
    }
    if (j>=t.length)
                return(i-t.length);       
    else
                return(-1);                     
}

关于KMP算法它的思路我了解了，但是关于它的代码我没有看懂，它是怎么利用next数组找到相等前后缀的？又是怎么让字符串完成移动的？看不懂的地方写在代码的注释部分，麻烦大佬们帮我讲一讲&#128557;

wsx666946 发表于 2022-7-9 22:00:17

{:10_266:}{:10_266:}{:10_266:}{:10_266:}{:10_266:}{:10_266:}

wsx666946 发表于 2022-7-9 22:56:34

大佬们快来呀

wsx666946 发表于 2022-7-11 21:39:16

为啥kmp算法是定义i,j相同 而不是跟next数组一样i=1.j=0开始呢

黎羽轩 发表于 2022-7-18 08:41:12

建议去B站看看有关KMP的Next数组的求法，有手推算和代码哦
页: [1]
查看完整版本: 有关kmp算法问题