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

gem456

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

#include<iostream>
using namespace std;
#include<string>
#define OK 1
#define ERROR 0
#define MAXLEN  200

typedef struct
{
        char ch[MAXLEN+1];
        int length;

}SString;

int index_KMP(SString S,SString T,int pos)
{
        int i=pos; int j=1; int next[100];
        while(i<=S.length && j<=S.length)
        {
                if(j==0||S.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                }
                else j=next[j];
        }
        if(j>T.length) return i-T.length;
        else return 0;
}

void get_next(SString T,int next[])
{
        int i=1; next[1]=0;int j=0;
        while(i<T.length)
        {
                if(j==0||T.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                        next[i]=j;
                }
                else j=next[j];
        }
}


int main()
{
        SString S,T;
        int pos;
        cin>>S.ch;
        cin>>T.ch;
        pos=index_KMP(S,T,1);
        cout<<pos<<endl;     //   输出pos时的值不符合常规
        system("pause");
        return 0;
}

最佳答案

月排行榜 / 总排行榜

不知道叫什么

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会导致双方第一次匹配时第一个字符串匹配不到。
以下是我的代码：

应用程序的入口点。
//测试数据：字符串：cddcdc 
//子串：cdc 
// 输出结果：4

#include "stdafx.h"

#include<iostream>
using namespace std;
#include<string>
#define OK 1
#define ERROR 0
#define MAXLEN  200

typedef struct
{
        char ch[MAXLEN+1];
        int length;

}SString;

void get_next(SString T,int *next)
{
        int i=1; next[1]=0;int j=0;
                while(i<strlen(T.ch))
        {
                if(j==0||T.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                        next[i]=j;
                }
                else j=next[j];
        }
}

int index_KMP(SString S,SString T,int pos)
{
        int i=pos; int j=0; int next[100];
                get_next(T,next);
        while(i<=strlen(S.ch)&& j<=strlen(S.ch))
        {
                if(j==0||S.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                }
                else j=next[j];
        }
        if(j>strlen(T.ch)) return (i-strlen(T.ch));
        else return 0;
}




int _tmain(int argc, _TCHAR* argv[])
{
         SString S,T;
        int pos=0;
        cin>>S.ch;
        cin>>T.ch;
        pos=index_KMP(S,T,pos);
        cout<<pos<<endl;     //   输出pos时的值不符合常规
        system("pause");
        return 0;
}

跳转到最佳答案楼层

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会导致双方第一次匹配时第一个字符串匹配不到。
以下是我的代码：

应用程序的入口点。
//测试数据：字符串：cddcdc 
//子串：cdc 
// 输出结果：4

#include "stdafx.h"

#include<iostream>
using namespace std;
#include<string>
#define OK 1
#define ERROR 0
#define MAXLEN  200

typedef struct
{
        char ch[MAXLEN+1];
        int length;

}SString;

void get_next(SString T,int *next)
{
        int i=1; next[1]=0;int j=0;
                while(i<strlen(T.ch))
        {
                if(j==0||T.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                        next[i]=j;
                }
                else j=next[j];
        }
}

int index_KMP(SString S,SString T,int pos)
{
        int i=pos; int j=0; int next[100];
                get_next(T,next);
        while(i<=strlen(S.ch)&& j<=strlen(S.ch))
        {
                if(j==0||S.ch[i]==T.ch[j])
                {
                        ++i;
                        ++j;
                }
                else j=next[j];
        }
        if(j>strlen(T.ch)) return (i-strlen(T.ch));
        else return 0;
}




int _tmain(int argc, _TCHAR* argv[])
{
         SString S,T;
        int pos=0;
        cin>>S.ch;
        cin>>T.ch;
        pos=index_KMP(S,T,pos);
        cout<<pos<<endl;     //   输出pos时的值不符合常规
        system("pause");
        return 0;
}