KMP优化算法求出的next数组错误

付笑

1. //预定义常量和类型
   
2. 
   
3. //函数结果状态代码
   
4. #include <stdio.h>
   
5. #include<stdlib.h>
   
6. #include <time.h>
   
7. #include<windows.h>
   
8. #include<math.h>
   
9. //#include<unistd.h>
   
10. #define TRUE 1
    
11. #define FALSE 0
    
12. #define OK 1
    
13. #define ERROR 0
    
14. #define INFEASIBLE -1
    
15. #define OVERFLOW -2
    
16. typedef int Status;
    
17. #define MAX_STR_LEN 255
    
18. 
    
19. typedef unsigned char String[MAX_STR_LEN+1];
    
20. 
    
21. Status StrAssign(String T,char *chars)
    
22. {
    
23. //生成一个其值等于chars的串T
    
24. int i;
    
25. if(strlen(chars)>MAX_STR_LEN)
    
26. {
    
27. return ERROR;
    
28. }
    
29. else
    
30. {
    
31. T[0]=strlen(chars);//0号单元存放串的长度
    
32. for(i=1;i<=T[0];i++)//从1号单元起复制串的内容
    
33. {
    
34. T[i]=*(chars+i-1);
    
35. }
    
36. return OK;
    
37. }
    
38. 
    
39. }
    
40. 
    
41. void get_next( String T, int *next )
    
42. {
    
43. int j = 0;
    
44. int i = 1;
    
45. next[1] = 0;
    
46. 
    
47. while( i < T[0] )
    
48. {
    
49. if( 0 == j || T[i] == T[j] )
    
50. {
    
51. i++;
    
52. j++;
    
53. if( T[i] != T[j] )
    
54. {
    
55. next[i] = j;
    
56. }
    
57. else
    
58. {
    
59. next[i] = next[j];
    
60. }
    
61. }
    
62. else
    
63. {
    
64. j = next[j];
    
65. }
    
66. }
    
67. 
    
68. for(i=1;i<=T[0];i++)
    
69. {
    
70. printf("%d ",next[i]);
    
71. }
    
72. printf("\n");
    
73. }
    
74. 
    
75. // 杩斿洖瀛愪覆T鍦ㄤ富涓睸绗琾os涓�瀛楃�︿箣鍚庣殑浣嶇疆
    
76. // 鑻ヤ笉瀛樺湪锛屽垯杩斿洖0
    
77. int Index_KMP( String S, String T, int pos )
    
78. {
    
79. int i = pos;
    
80. int j = 1;
    
81. int next[255];
    
82. 
    
83. get_next( T, next );
    
84. 
    
85. while( i <= S[0] && j <= T[0] )
    
86. {
    
87. if( 0 == j || S[i] == T[j] )
    
88. {
    
89. i++;
    
90. j++;
    
91. }
    
92. else
    
93. {
    
94. j = next[j];
    
95. }
    
96. }
    
97. 
    
98. if( j > T[0] )
    
99. {
    
100. return i - T[0];
     
101. }
     
102. else
     
103. {
     
104. return 0;
     
105. }
     
106. }
     
107. 
     
108. main()
     
109. {
     
110. char *chars1="ababaaaba"; //这里赋值给T
     
111. char *chars2="fababcabdabababaaabacabeabababe";
     
112. String T,S;
     
113. int next[255];
     
114. 
     
115. StrAssign(T,chars1);
     
116. StrAssign(S,chars2);
     
117. 
     
118. get_next(T, next );
     
119. 
     
120. return 0;
     
121. }
     

复制代码

模式串T="ababaaaba"
优化算法得出的next数组=0 1 0 1 0 4 2 1 0
正确的next数组应该    是=0 1 1 2 3 4 2 2 3

请问是为什么，是算法错了吗

付笑

谁帮我看下啊

付笑

谁帮下我啊

付笑

没有问题了，两个数组都可以得到一样的匹配结果，昨天支行时老出错，今天就可以了，谢谢大家，问题解决了