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

DarrenTitor

1. void build_array(char* substr, int length)
   
2. {
   
3.        
   
4.         int* sub_array = (int*)malloc((length+1)*sizeof(int));
   
5.         for(int a=0; a<=length+1;a++)
   
6.         {
   
7.                     sub_array[a] = 0;
   
8.         }
   
9.         int i = 1;
   
10.         int j = 0;
    
11.         while(i<=length)
    
12.         {
    
13.                     if (substr[j]==substr[i])
    
14.                     {
    
15.                                 sub_array[i] ++;
    
16.                                 i++;
    
17.                                 j++;
    
18.                     }
    
19.                     else
    
20.                     {
    
21.                                 j = 0;
    
22.                     }
    
23.         }
    
24. 
    
25.         //test the sub_array
    
26.         printf("\nThe sub_array so far is :\n");
    
27.         for(int k = 0; k<=length; k++)
    
28.         {
    
29.                     printf("%d ", sub_array[k]);
    
30.         }
    
31.         printf("\n");
    
32.        
    
33. }

复制代码

思路如下：

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



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

82457097

这是写next数组？

Croper

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

1.         while(i<=length)
   
2.         {
   
3.                     if (substr[j]==substr[i])
   
4.                     {
   
5.                                 sub_array[i] ++;
   
6.                                 i++;
   
7.                                 j++;
   
8.                     }
   
9.                     else
   
10.                     {
    
11.                                 j = 0;
    
12.                     }
    
13.         }

复制代码

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

DarrenTitor

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

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