我这个kmp算法，在中间有可以匹配的值，但是最后运行的时候没有结果。救命

划句顾

1. /*******
   
2. *author :LaoGu
   
3. *time   :2021/10/31
   
4. *fuction:模式匹配串--KMP算法
   
5. *******/
   
6. #include<iostream>
   
7. #include<string.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define MAXSIZE 100
    
12. 
    
13. typedef struct{
    
14.   char ch[MAXSIZE+1];
    
15.   int length;
    
16. }SString;
    
17. 
    
18. void get_next(SString T,int *next)
    
19. {
    
20.         int i = 1,j=0;
    
21.         next[1]=0;
    
22.         while(i<T.length)
    
23.         {
    
24.                 if(j==0||T.ch[i]==T.ch[j])
    
25.                 {
    
26.                         ++i;
    
27.                         ++j;
    
28.                         if(T.ch[i]!=T.ch[j])
    
29.                         {
    
30.                                 next[i] = j;
    
31.                         }
    
32.                         else
    
33.                         {
    
34.                                 next[i] = next[j];
    
35.                         }
    
36.                 }
    
37.                 else{
    
38.                         j = next[j];
    
39.                 }
    
40.         }
    
41. 
    
42. }
    
43. 
    
44. int index_KMP(SString S,SString T,int pos){
    
45.    int i = pos,j = 1;
    
46.    int next[255];
    
47.    get_next(T,next);
    
48.    while(i<=S.length && j<=T.length){
    
49.      if(j==0||S.ch[i]==T.ch[j])
    
50.          {
    
51.                  ++i;
    
52.                  ++j;
    
53.          }
    
54.          else{
    
55.                  j = next[j];
    
56.          }
    
57.    }
    
58. 
    
59.     if(j>=T.length)
    
60.            return i-T.length;  //匹配成功
    
61.    else
    
62.        return 0;  //匹配失败
    
63. }
    
64. 
    
65. int main(){
    
66.         SString S,T;
    
67. 
    
68.         printf("请输入母串：");
    
69.         cin>>S.ch;   
    
70.         S.length = strlen(S.ch);
    
71. 
    
72.         printf("请输入子串：");
    
73.         cin>>T.ch;
    
74.         T.length = strlen(T.ch);
    
75. 
    
76.         int t = index_KMP(S,T,1);
    
77.         if(t){
    
78.             printf("在[%d]的地方成功匹配\n",t);
    
79.         }
    
80.         else("匹配失败！！！\n");
    
81.         return 0;
    
82. }

复制代码

                               
登录/注册后可看大图

在末尾的值就可以匹配，但是在中间可以匹配的这种情况就不行了


还有这种情况，明明没有匹配的值，但是它却有结果。

                               
登录/注册后可看大图

希望各位大佬，能在我的代码的基础上修改，孩子头要秃了

划句顾

我重新搞了一个
代码如下：

1. /*
   
2. *author : laogu
   
3. *time   :2021/11/1
   
4. *fuction:kmp算法
   
5. */
   
6. #include<iostream>
   
7. #include<string.h>
   
8. 
   
9. using namespace std;
   
10. 
    
11. //next 函数
    
12. void get_next(char *T,int *next,int lent)  
    
13. {
    
14.         int i = 1,j = 0;
    
15.         next[1]=0;
    
16.         while(i<lent)
    
17.         {
    
18.             if(j==0||T[i]==T[j])
    
19.         {
    
20.             ++i;
    
21.             ++j;
    
22.         if(T[i]!=T[j])
    
23.         {
    
24.             next[i] = j;
    
25.         }
    
26.         else   //当相邻的字符相等的情况下，加了这个可以避免漏掉一些信息
    
27.         {
    
28.             next[i] = next[j];
    
29.         }
    
30.         }
    
31.         else{
    
32.              j = next[j];
    
33.             }
    
34.     }       
    
35. }
    
36. 
    
37. //KMP算法
    
38. int Index_KMP(char *S,char *T,int lens,int lent)
    
39. {
    
40.      int i = 0,j = 0;
    
41.      int next[255];
    
42.      get_next(T,next,lent);
    
43.      while(i<lens && j<lent){
    
44.      if(j==0||S[i]==T[j])
    
45.          {
    
46.             ++i;
    
47.             ++j;
    
48.          }
    
49.          else{
    
50.               j = next[j];
    
51.          }
    
52.    }
    
53. 
    
54.     if(j==lent)   
    
55.            return i-lent+1;  //匹配成功
    
56.    else
    
57.        return 0;  //匹配失败
    
58. }
    
59. 
    
60. //主函数
    
61. int main()
    
62. {
    
63.     char S[30],T[20];  //定义两个串
    
64.    
    
65.     cout<<"请输入主串S: ";
    
66.     scanf("%s",&S);    //必须是%s,如果是%c的话，不能输入一大串的字符
    
67. 
    
68.     cout<<"请输入字串T: ";
    
69.     scanf("%s",&T);
    
70.    
    
71.     int lent,lens;     //字符串的长度
    
72.     lens =  strlen(S);  //母串的长度
    
73.     lent =  strlen(T);  //子串的长度
    
74. 
    
75.     int t = Index_KMP(S,T,lens,lent);     
    
76.     printf("子串从主串的第%d位开始匹配成功!\n",t);
    
77.     return 0;
    
78. }

复制代码

                               
登录/注册后可看大图

不过，我觉得这个新的代码有点长，运行有点慢。但是我就只能搞这个

                               
登录/注册后可看大图

运行结果：

                               
登录/注册后可看大图

希望各位鱼油萌，可以搞个简单易懂的代码分享一下，头秃了

划句顾

划句顾 发表于 2021-11-1 23:01
我重新搞了一个
代码如下：

但是我现在觉得这个新的有点问题！！！算了不管了，先交作业再说了

划句顾

划句顾 发表于 2021-11-1 23:01
我重新搞了一个
代码如下：

这个真的有问题

lei1996

数据结构让人头秃

划句顾

lei1996 发表于 2021-11-2 09:55
数据结构让人头秃

如果写不出来还好，东西写出来后一堆错误才要命

lei1996

划句顾 发表于 2021-11-2 10:16
如果写不出来还好，东西写出来后一堆错误才要命

老实说  我一直没看懂你的next数组怎么构建的

划句顾

lei1996 发表于 2021-11-2 11:10
老实说  我一直没看懂你的next数组怎么构建的

说实话，我写完我都懵了

tomok

看下 数据结构