KMP算法的实现

道化師

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. //给char * 起名为String
   
5. typedef char* String;
   
6. 
   
7. //定义一个结构体，str存储字符串，cap存储字符串的长度
   
8. typedef struct
   
9. {
   
10.         char str[255];
    
11.         int cap;
    
12. }Str;
    
13. 
    
14. //获取next数组，这个是KMP算法的灵魂
    
15. void get_next(Str *T, int *next )
    
16. {
    
17.         int j = 0;
    
18.         int i = 1;
    
19.         next[1] = 0;
    
20.         
    
21.         while( i < T->str[0] )   //当循环次数超过字符串的长度的时候退出循环
    
22.         {
    
23.                 if( 0 == j || T->str[i] == T->str[j] )
    
24.                 {
    
25.                         i++;
    
26.                         j++;
    
27.                         if( T->str[i] != T->str[j] )    //改进后的算法
    
28.                         {
    
29.                                 next[i] = j;
    
30.                         }
    
31.                         else
    
32.                         {
    
33.                                 next[i] = next[j];
    
34.                         }
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         j = next[j];
    
39.                 }
    
40.         }
    
41. }
    
42. 
    
43. // 返回子串T在主串S第pos个字符之后的位置
    
44. // 若不存在，则返回0
    
45. int Index_KMP( Str *S, Str *T, int pos )
    
46. {
    
47.         int i = pos;
    
48.         int j = 1;
    
49.         int next[255];
    
50.         
    
51.         get_next( T, next );
    
52.         
    
53.         while( i <= S->cap && j <= T->cap)
    
54.         {
    
55.         //增加判断，防止特殊情况发生
    
56.                 if( 0 == j || S->str[i] == T->str[j] )
    
57.                 {
    
58.                         i++;
    
59.                         j++;
    
60.                 }
    
61.                 else
    
62.                 {
    
63.                         j = next[j];
    
64.                 }
    
65.         }
    
66.         
    
67.         if( j > T->cap )
    
68.         {
    
69.                 return i - T->cap;
    
70.         }
    
71.         else
    
72.         {
    
73.                 return 0;
    
74.         }
    
75. }
    
76. 
    
77. //创建存储容量和字符串的结构，这里需要改变结构体的内容，所以传入指向指针的指针
    
78. void CreateStr(Str **S)
    
79. {
    
80.         *S = (Str *)malloc(sizeof (Str));
    
81.         if (!S)
    
82.         {
    
83.                 perror("INIT:malloc");
    
84.                 exit(EXIT_FAILURE);
    
85.         }
    
86.         
    
87.         printf("请输入一个字符串，输入回车结束：");
    
88.         char ch;
    
89.         int i = 0;
    
90.         
    
91.         while ((ch = getchar()) != '\n')
    
92.         {
    
93.                 (*S)->str[i++] = ch;     //后置++，先赋值，后++
    
94.         }
    
95.         //这里i相当与字符串的长度
    
96.         (*S)->cap = i;
    
97.         
    
98. }
    
99. 
    
100. int main(void)
     
101. {
     
102.         Str *S = NULL;
     
103.         Str *T = NULL;
     
104.         int pos = 1;
     
105.         int status = 0;
     
106.         
     
107.         CreateStr(&S);
     
108.         CreateStr(&T);
     
109.         
     
110.         status = Index_KMP(S, T, pos);
     
111.         
     
112.         if (1 == status)
     
113.         {
     
114.                 printf("是");
     
115.         }
     
116.         else
     
117.         {
     
118.                 printf("否");        
     
119.         }
     
120.         

复制代码

FishC

这段代码实现了KMP算法，用来查找子串在主串中的位置。不过代码中有一些错误和不完善的地方，我来帮你解决。

首先，在函数get_next()中，你需要将next定义为数组，而不是整数。next数组存储的是匹配失败时下一次比较的位置，所以它的长度应该与字符串T的长度相同。修改代码如下：

1. void get_next(Str *T, int *next )
   
2. {
   
3.         int j = 0;
   
4.         int i = 1;
   
5.         next[0] = 0; // 初始化next[0]为0
   
6.         
   
7.         while( i < T->cap )   //修改为cap
   
8.         {
   
9.                 if( 0 == j || T->str[i-1] == T->str[j-1] ) // 修改为str[i-1]和str[j-1]
   
10.                 {
    
11.                         i++;
    
12.                         j++;
    
13.                         if( T->str[i-1] != T->str[j-1] )    //改进后的算法
    
14.                         {
    
15.                                 next[i] = j;
    
16.                         }
    
17.                         else
    
18.                         {
    
19.                                 next[i] = next[j];
    
20.                         }
    
21.                 }
    
22.                 else
    
23.                 {
    
24.                         j = next[j];
    
25.                 }
    
26.         }
    
27. }

复制代码

接下来，在函数Index_KMP()中，你需要对pos的取值进行判断，保证在合法范围内。修改代码如下：

1. int Index_KMP( Str *S, Str *T, int pos )
   
2. {
   
3.         if (pos < 1 || pos > S->cap) {
   
4.                 return 0; // pos超出范围，直接返回0
   
5.         }
   
6.         
   
7.         int i = pos;
   
8.         int j = 1;
   
9.         int next[T->cap];
   
10.         
    
11.         get_next( T, next );
    
12.         
    
13.         while( i <= S->cap && j <= T->cap)  // 小于等于号
    
14.         {
    
15.                 if( j == 0 || S->str[i-1] == T->str[j-1] ) // 修改为str[i-1]和str[j-1]
    
16.                 {
    
17.                         i++;
    
18.                         j++;
    
19.                 }
    
20.                 else
    
21.                 {
    
22.                         j = next[j];
    
23.                 }
    
24.         }
    
25.         
    
26.         if( j > T->cap )
    
27.         {
    
28.                 return i - T->cap;
    
29.         }
    
30.         else
    
31.         {
    
32.                 return 0;
    
33.         }
    
34. }

复制代码

最后，在函数CreateStr()中，你没有为字符数组分配内存空间。修改代码如下：

1. void CreateStr(Str **S)
   
2. {
   
3.         *S = (Str *)malloc(sizeof (Str));
   
4.         if (!(*S))
   
5.         {
   
6.                 perror("INIT:malloc");
   
7.                 exit(EXIT_FAILURE);
   
8.         }
   
9. 
   
10.         printf("请输入一个字符串，输入回车结束：");
    
11. 
    
12.         int size = 10; // 假定初始容量为10
    
13.         int length = 0; // 用于记录字符串的长度
    
14.         char ch;
    
15. 
    
16.         (*S)->str = (char *)malloc(sizeof(char) * size); // 分配初始内存空间
    
17. 
    
18.         if (!((*S)->str))
    
19.         {
    
20.                 perror("INIT:malloc");
    
21.                 exit(EXIT_FAILURE);
    
22.         }
    
23. 
    
24.         while ((ch = getchar()) != '\n')
    
25.         {
    
26.                 (*S)->str[length] = ch;
    
27.                 length++;
    
28. 
    
29.                 if (length == size) // 当存储空间不够时，动态扩展内存
    
30.                 {
    
31.                         size *= 2;
    
32.                         (*S)->str = (char *)realloc((*S)->str, sizeof(char) * size);
    
33.                         
    
34.                         if (!((*S)->str))
    
35.                         {
    
36.                                 perror("INIT:realloc");
    
37.                                 exit(EXIT_FAILURE);
    
38.                         }
    
39.                 }
    
40.         }
    
41. 
    
42.         (*S)->cap = length; // 字符串的长度就是数组的大小
    
43. }

复制代码

现在，你可以重新运行程序测试KMP算法了。记得在程序结束前，释放动态分配的内存空间，避免内存泄漏。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

kerln888

学习了

芜湖666

sdf