[已解决]kmp算法遇到一些小问题

gem456

打算输出匹配的位置，结果程序运行时打出一个很长的数字，即乱码 求帮助

1. #include<iostream>
   
2. using namespace std;
   
3. #include<string>
   
4. #define OK 1
   
5. #define ERROR 0
   
6. #define MAXLEN  200
   
7. 
   
8. typedef struct
   
9. {
   
10.         char ch[MAXLEN+1];
    
11.         int length;
    
12. 
    
13. }SString;
    
14. 
    
15. int index_KMP(SString S,SString T,int pos)
    
16. {
    
17.         int i=pos; int j=1; int next[100];
    
18.         while(i<=S.length && j<=S.length)
    
19.         {
    
20.                 if(j==0||S.ch[i]==T.ch[j])
    
21.                 {
    
22.                         ++i;
    
23.                         ++j;
    
24.                 }
    
25.                 else j=next[j];
    
26.         }
    
27.         if(j>T.length) return i-T.length;
    
28.         else return 0;
    
29. }
    
30. 
    
31. void get_next(SString T,int next[])
    
32. {
    
33.         int i=1; next[1]=0;int j=0;
    
34.         while(i<T.length)
    
35.         {
    
36.                 if(j==0||T.ch[i]==T.ch[j])
    
37.                 {
    
38.                         ++i;
    
39.                         ++j;
    
40.                         next[i]=j;
    
41.                 }
    
42.                 else j=next[j];
    
43.         }
    
44. }
    
45. 
    
46. 
    
47. int main()
    
48. {
    
49.         SString S,T;
    
50.         int pos;
    
51.         cin>>S.ch;
    
52.         cin>>T.ch;
    
53.         pos=index_KMP(S,T,1);
    
54.         cout<<pos<<endl;     //   输出pos时的值不符合常规
    
55.         system("pause");
    
56.         return 0;
    
57. }

复制代码

最佳答案

月排行榜 / 总排行榜

不知道叫什么

2016-5-31 14:40:52

c语言里面表示长度要用strlen(“S")或者sizeof("S"),不同的是使用sizeof多了一个字符串结束符\0
你这里面试定义了一个结构体，所以应用strlen(S.ch)
如果直接用S.length,返回的是一个地址，所以会跳过你的18句直接跳到27句执行，所以你的一大段"乱码"其实是1-（-地址码）得到的结果。
另外上面正常的话执行到25句也会出错，因为你的next[j]数组没有初始化
所以需要先加上调用get_next()函数
另外next[]数组是从next[0]开始存放数据的，所以把i和j赋值为1会导致双方第一次匹配时第一个字符串匹配不到。
以下是我的代码：

1. 应用程序的入口点。
   
2. //测试数据：字符串：cddcdc
   
3. //子串：cdc
   
4. // 输出结果：4
   
5. 
   
6. #include "stdafx.h"
   
7. 
   
8. #include<iostream>
   
9. using namespace std;
   
10. #include<string>
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define MAXLEN  200
    
14. 
    
15. typedef struct
    
16. {
    
17.         char ch[MAXLEN+1];
    
18.         int length;
    
19. 
    
20. }SString;
    
21. 
    
22. void get_next(SString T,int *next)
    
23. {
    
24.         int i=1; next[1]=0;int j=0;
    
25.                 while(i<strlen(T.ch))
    
26.         {
    
27.                 if(j==0||T.ch[i]==T.ch[j])
    
28.                 {
    
29.                         ++i;
    
30.                         ++j;
    
31.                         next[i]=j;
    
32.                 }
    
33.                 else j=next[j];
    
34.         }
    
35. }
    
36. 
    
37. int index_KMP(SString S,SString T,int pos)
    
38. {
    
39.         int i=pos; int j=0; int next[100];
    
40.                 get_next(T,next);
    
41.         while(i<=strlen(S.ch)&& j<=strlen(S.ch))
    
42.         {
    
43.                 if(j==0||S.ch[i]==T.ch[j])
    
44.                 {
    
45.                         ++i;
    
46.                         ++j;
    
47.                 }
    
48.                 else j=next[j];
    
49.         }
    
50.         if(j>strlen(T.ch)) return (i-strlen(T.ch));
    
51.         else return 0;
    
52. }
    
53. 
    
54. 
    
55. 
    
56. 
    
57. int _tmain(int argc, _TCHAR* argv[])
    
58. {
    
59.          SString S,T;
    
60.         int pos=0;
    
61.         cin>>S.ch;
    
62.         cin>>T.ch;
    
63.         pos=index_KMP(S,T,pos);
    
64.         cout<<pos<<endl;     //   输出pos时的值不符合常规
    
65.         system("pause");
    
66.         return 0;
    
67. }
    

复制代码

跳转到最佳答案楼层

zhouxcpython

好文章 感谢share

不知道叫什么

c语言里面表示长度要用strlen(“S")或者sizeof("S"),不同的是使用sizeof多了一个字符串结束符\0
你这里面试定义了一个结构体，所以应用strlen(S.ch)
如果直接用S.length,返回的是一个地址，所以会跳过你的18句直接跳到27句执行，所以你的一大段"乱码"其实是1-（-地址码）得到的结果。
另外上面正常的话执行到25句也会出错，因为你的next[j]数组没有初始化
所以需要先加上调用get_next()函数
另外next[]数组是从next[0]开始存放数据的，所以把i和j赋值为1会导致双方第一次匹配时第一个字符串匹配不到。
以下是我的代码：

1. 应用程序的入口点。
   
2. //测试数据：字符串：cddcdc
   
3. //子串：cdc
   
4. // 输出结果：4
   
5. 
   
6. #include "stdafx.h"
   
7. 
   
8. #include<iostream>
   
9. using namespace std;
   
10. #include<string>
    
11. #define OK 1
    
12. #define ERROR 0
    
13. #define MAXLEN  200
    
14. 
    
15. typedef struct
    
16. {
    
17.         char ch[MAXLEN+1];
    
18.         int length;
    
19. 
    
20. }SString;
    
21. 
    
22. void get_next(SString T,int *next)
    
23. {
    
24.         int i=1; next[1]=0;int j=0;
    
25.                 while(i<strlen(T.ch))
    
26.         {
    
27.                 if(j==0||T.ch[i]==T.ch[j])
    
28.                 {
    
29.                         ++i;
    
30.                         ++j;
    
31.                         next[i]=j;
    
32.                 }
    
33.                 else j=next[j];
    
34.         }
    
35. }
    
36. 
    
37. int index_KMP(SString S,SString T,int pos)
    
38. {
    
39.         int i=pos; int j=0; int next[100];
    
40.                 get_next(T,next);
    
41.         while(i<=strlen(S.ch)&& j<=strlen(S.ch))
    
42.         {
    
43.                 if(j==0||S.ch[i]==T.ch[j])
    
44.                 {
    
45.                         ++i;
    
46.                         ++j;
    
47.                 }
    
48.                 else j=next[j];
    
49.         }
    
50.         if(j>strlen(T.ch)) return (i-strlen(T.ch));
    
51.         else return 0;
    
52. }
    
53. 
    
54. 
    
55. 
    
56. 
    
57. int _tmain(int argc, _TCHAR* argv[])
    
58. {
    
59.          SString S,T;
    
60.         int pos=0;
    
61.         cin>>S.ch;
    
62.         cin>>T.ch;
    
63.         pos=index_KMP(S,T,pos);
    
64.         cout<<pos<<endl;     //   输出pos时的值不符合常规
    
65.         system("pause");
    
66.         return 0;
    
67. }
    

复制代码