我这个kmp算法，在中间有可以匹配的值，但是最后运行的时候没有结果。救命
/********author :LaoGu
*time :2021/10/31
*fuction:模式匹配串--KMP算法
*******/
#include<iostream>
#include<string.h>
using namespace std;
#define MAXSIZE 100
typedef struct{
char ch;
int length;
}SString;
void get_next(SString T,int *next)
{
int i = 1,j=0;
next=0;
while(i<T.length)
{
if(j==0||T.ch==T.ch)
{
++i;
++j;
if(T.ch!=T.ch)
{
next = j;
}
else
{
next = next;
}
}
else{
j = next;
}
}
}
int index_KMP(SString S,SString T,int pos){
int i = pos,j = 1;
int next;
get_next(T,next);
while(i<=S.length && j<=T.length){
if(j==0||S.ch==T.ch)
{
++i;
++j;
}
else{
j = next;
}
}
if(j>=T.length)
return i-T.length;//匹配成功
else
return 0;//匹配失败
}
int main(){
SString S,T;
printf("请输入母串：");
cin>>S.ch;
S.length = strlen(S.ch);
printf("请输入子串：");
cin>>T.ch;
T.length = strlen(T.ch);
int t = index_KMP(S,T,1);
if(t){
printf("在[%d]的地方成功匹配\n",t);
}
else("匹配失败！！！\n");
return 0;
}
static/image/hrline/5.gif
在末尾的值就可以匹配，但是在中间可以匹配的这种情况就不行了
还有这种情况，明明没有匹配的值，但是它却有结果。
static/image/hrline/5.gif
希望各位大佬，能在我的代码的基础上修改，孩子头要秃了{:5_100:} 本帖最后由 划句顾 于 2021-11-1 23:07 编辑
我重新搞了一个{:5_109:}
代码如下：
/*
*author : laogu
*time :2021/11/1
*fuction:kmp算法
*/
#include<iostream>
#include<string.h>
using namespace std;
//next 函数
void get_next(char *T,int *next,int lent)
{
int i = 1,j = 0;
next=0;
while(i<lent)
{
if(j==0||T==T)
{
++i;
++j;
if(T!=T)
{
next = j;
}
else //当相邻的字符相等的情况下，加了这个可以避免漏掉一些信息
{
next = next;
}
}
else{
j = next;
}
}
}
//KMP算法
int Index_KMP(char *S,char *T,int lens,int lent)
{
int i = 0,j = 0;
int next;
get_next(T,next,lent);
while(i<lens && j<lent){
if(j==0||S==T)
{
++i;
++j;
}
else{
j = next;
}
}
if(j==lent)
return i-lent+1;//匹配成功
else
return 0;//匹配失败
}
//主函数
int main()
{
char S,T;//定义两个串
cout<<"请输入主串S: ";
scanf("%s",&S); //必须是%s,如果是%c的话，不能输入一大串的字符
cout<<"请输入字串T: ";
scanf("%s",&T);
int lent,lens; //字符串的长度
lens =strlen(S);//母串的长度
lent =strlen(T);//子串的长度
int t = Index_KMP(S,T,lens,lent);
printf("子串从主串的第%d位开始匹配成功!\n",t);
return 0;
}
static/image/hrline/5.gif
不过，我觉得这个新的代码有点长，运行有点慢。但是我就只能搞这个{:5_100:}
static/image/hrline/5.gif
运行结果：
static/image/hrline/5.gif
希望各位鱼油萌，可以搞个简单易懂的代码分享一下，头秃了{:5_100:} 划句顾 发表于 2021-11-1 23:01
我重新搞了一个
代码如下：
{:10_261:}但是我现在觉得这个新的有点问题{:10_243:}！！！算了不管了，先交作业再说了{:10_256:} 划句顾 发表于 2021-11-1 23:01
我重新搞了一个
代码如下：
这个真的有问题{:10_247:} 数据结构让人头秃{:10_256:} lei1996 发表于 2021-11-2 09:55
数据结构让人头秃
{:10_291:}
如果写不出来还好，东西写出来后一堆错误才要命{:10_251:} 划句顾 发表于 2021-11-2 10:16
如果写不出来还好，东西写出来后一堆错误才要命
老实说我一直没看懂你的next数组怎么构建的{:10_307:} lei1996 发表于 2021-11-2 11:10
老实说我一直没看懂你的next数组怎么构建的
说实话，我写完我都懵了{:10_262:} 看下 数据结构
页:
[1]