kmp算法遇到一些小问题
打算输出匹配的位置，结果程序运行时打出一个很长的数字，即乱码 求帮助#include<iostream>
using namespace std;
#include<string>
#define OK 1
#define ERROR 0
#define MAXLEN200
typedef struct
{
char ch;
int length;
}SString;
int index_KMP(SString S,SString T,int pos)
{
int i=pos; int j=1; int next;
while(i<=S.length && j<=S.length)
{
if(j==0||S.ch==T.ch)
{
++i;
++j;
}
else j=next;
}
if(j>T.length) return i-T.length;
else return 0;
}
void get_next(SString T,int next[])
{
int i=1; next=0;int j=0;
while(i<T.length)
{
if(j==0||T.ch==T.ch)
{
++i;
++j;
next=j;
}
else j=next;
}
}
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;
}
好文章 感谢share c语言里面表示长度要用strlen(“S")或者sizeof("S"),不同的是使用sizeof多了一个字符串结束符\0
你这里面试定义了一个结构体，所以应用strlen(S.ch)
如果直接用S.length,返回的是一个地址，所以会跳过你的18句直接跳到27句执行，所以你的一大段"乱码"其实是1-（-地址码）得到的结果。
另外上面正常的话执行到25句也会出错，因为你的next数组没有初始化
所以需要先加上调用get_next()函数
另外next[]数组是从next开始存放数据的，所以把i和j赋值为1会导致双方第一次匹配时第一个字符串匹配不到。
以下是我的代码：应用程序的入口点。
//测试数据：字符串：cddcdc
//子串：cdc
// 输出结果：4
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<string>
#define OK 1
#define ERROR 0
#define MAXLEN200
typedef struct
{
char ch;
int length;
}SString;
void get_next(SString T,int *next)
{
int i=1; next=0;int j=0;
while(i<strlen(T.ch))
{
if(j==0||T.ch==T.ch)
{
++i;
++j;
next=j;
}
else j=next;
}
}
int index_KMP(SString S,SString T,int pos)
{
int i=pos; int j=0; int next;
get_next(T,next);
while(i<=strlen(S.ch)&& j<=strlen(S.ch))
{
if(j==0||S.ch==T.ch)
{
++i;
++j;
}
else j=next;
}
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;
}
页:
[1]