KMP生成字串数组时遇到了bug

DarrenTitor

void build_array(char* substr, int length)
{
        
        int* sub_array = (int*)malloc((length+1)*sizeof(int));
        for(int a=0; a<=length+1;a++)
        {
                    sub_array[a] = 0;
        }
        int i = 1;
        int j = 0;
        while(i<=length)
        {
                    if (substr[j]==substr[i])
                    {
                                sub_array[i] ++;
                                i++;
                                j++;
                    }
                    else
                    {
                                j = 0;
                    }
        }

        //test the sub_array
        printf("\nThe sub_array so far is :\n");
        for(int k = 0; k<=length; k++)
        {
                    printf("%d ", sub_array[k]);
        }
        printf("\n");
        
}

思路如下：

建立数组
    字符子串与0~n的数组匹配
    j指向[0]，i指向[1]
        j字母==i字母
            i的数组值+1
            i右移，j右移
        j字母！=i字母
            j退回[0]位置，重新检查
            



问题出在while循环中，
请问各位能否帮我看下错在哪里，谢谢啦

82457097

这是写next数组？

Croper

你这next数组写的什么跟什么啊，

        while(i<=length)
        {
                    if (substr[j]==substr[i])
                    {
                                sub_array[i] ++;
                                i++;
                                j++;
                    }
                    else
                    {
                                j = 0;
                    }
        }

自己读一下，substr[0]！=substr[1]之后不直接死循环了

DarrenTitor

Croper 发表于 2019-4-25 10:56
你这next数组写的什么跟什么啊，
自己读一下，substr[0]！=substr[1]之后不直接死循环了

谢谢谢谢啦
还没看next数组怎么写hh
了解kmp大概思路之后想自己先试一下，再对比