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

划句顾

/*******
*author :LaoGu
*time   :2021/10/31
*fuction:模式匹配串--KMP算法
*******/
#include<iostream>
#include<string.h>

using namespace std;

#define MAXSIZE 100

typedef struct{
  char ch[MAXSIZE+1];
  int length;
}SString;

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

}

int index_KMP(SString S,SString T,int pos){
   int i = pos,j = 1;
   int next[255];
   get_next(T,next);
   while(i<=S.length && j<=T.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;  //匹配失败
}

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;
}

                               
登录/注册后可看大图

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


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

                               
登录/注册后可看大图

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

划句顾

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

/*
*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[1]=0;
        while(i<lent)
        {
            if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
        if(T[i]!=T[j])
        {
            next[i] = j;
        }
        else   //当相邻的字符相等的情况下，加了这个可以避免漏掉一些信息 
        {
            next[i] = next[j];
        }
        }
        else{
             j = next[j];
            }
    }        
} 

//KMP算法 
int Index_KMP(char *S,char *T,int lens,int lent)
{
     int i = 0,j = 0;
     int next[255];
     get_next(T,next,lent);
     while(i<lens && j<lent){
     if(j==0||S[i]==T[j])
         {
            ++i;
            ++j;
         }
         else{
              j = next[j];
         }
   }

    if(j==lent)    
           return i-lent+1;  //匹配成功
   else
       return 0;  //匹配失败
}

//主函数 
int main()
{
    char S[30],T[20];  //定义两个串 
    
    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;
}

                               
登录/注册后可看大图

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

                               
登录/注册后可看大图

运行结果：

                               
登录/注册后可看大图

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

划句顾

划句顾 发表于 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

看下 数据结构