qq_67362360 2022-08-15 15:05 采纳率: 50%
浏览 46
已结题

算法不知道出现了什么问题

-

SqString.h
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <iostream>
#define MAXSIZE 100
#define ElemType char

using namespace std;

typedef struct 
{
    ElemType data[MAXSIZE];
    int length;
}SqString;

//初始化
void  InitIndex(SqString &s){

    s.length=0;
}

//BF
int Index(SqString &s,SqString &t){
    int i=0,j=0;
    while(i<s.length&&j<t.length){
        if(s.data[i]==t.data[j]){
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=t.length){
        return (i-t.length);
    }else{
        return (-1);
    }
}

//next
void GetNext(SqString &t,int next[]){
    int j=0,k=-1;
    next[0]=-1;
    while(j<t.length-1){
        if(k==-1||t.data[j]==t.data[k]){
            j++;
            k++;
            next[j]=k;
        }else{
            k=next[k];
        }
    }
} 

//KMP
int KMPIndex(SqString &s,SqString &t){
    int i=0,j=0,next[MAXSIZE];
    GetNext(t,next);
    while(i<s.length&&j<t.length){
        if(j==-1||s.data[i]==t.data[j]){
            j++;
            i++;
        }else{
            j=next[j];
        }
    }
    if(j>=t.length){
        return (i-t.length);
    }else{
        return (-1);
    }
}




#include <iostream>
#include "SqString.h"

using namespace std;

int main() {
    SqString s,t;
    int a,a1,i;
    ElemType e1,e2;
    
    InitIndex(s);
    InitIndex(t);
    
    cout<<"请输入主串个数:"<<endl; 
    cin>>a;
    for(i=0;i<a;i++){
        cout<<"请输入主串的元素:";
        cin>>e1;
        s.data[i]=e1;
        
    }
    
    
    for(i=0;i<a;i++){
        cout<<s.data[i]<<"  ";

    }
    cout<<endl;
    
    
    cout<<"请输入子串个数:"<<endl; 
    cin>>a1;
    for(i=0;i<a1;i++){
        cout<<"请输入子串的元素:";
        cin>>e2;
        t.data[i]=e2;
    }
    for(i=0;i<a1;i++){
        cout<<t.data[i]<<"  ";
        
    }
    cout<<endl;
    
    cout<<"采用BF算法"<<endl;
    cout<<"第一个匹配的字符下标为:";
    Index(s,t);
    cout<<endl;
    
    cout<<"采用KMP算法"<<endl;
    cout<<"第一个匹配的字符下标为:";
    KMPIndex(s,t);
    return 0;
}


  • 写回答

4条回答 默认 最新

  • CSDN专家-link 2022-08-15 15:47
    关注

    两个问题,一是你没有给s和t的length赋值啊
    二是你调用Index(s,t)后,要获得它的返回值,然后如果返回值大于等于0,表示有匹配项,然后输出这个返回值

    SqString.h
    #include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    #include <iostream>
    #define MAXSIZE 100
    #define ElemType char
     
    using namespace std;
     
    typedef struct 
    {
        ElemType data[MAXSIZE];
        int length;
    }SqString;
     
    //初始化
    void  InitIndex(SqString &s){
     
        s.length=0;
    }
     
    //BF
    int Index(SqString &s,SqString &t){
        int i=0,j=0;
        while(i<s.length&&j<t.length){
            if(s.data[i]==t.data[j]){
                i++;
                j++;
            }else{
                i=i-j+1;
                j=0;
            }
        }
        if(j>=t.length){
            return (i-t.length);
        }else{
            return (-1);
        }
    }
     
    //next
    void GetNext(SqString &t,int next[]){
        int j=0,k=-1;
        next[0]=-1;
        while(j<t.length-1){
            if(k==-1||t.data[j]==t.data[k]){
                j++;
                k++;
                next[j]=k;
            }else{
                k=next[k];
            }
        }
    } 
     
    //KMP
    int KMPIndex(SqString &s,SqString &t){
        int i=0,j=0,next[MAXSIZE];
        GetNext(t,next);
        while(i<s.length&&j<t.length){
            if(j==-1||s.data[i]==t.data[j]){
                j++;
                i++;
            }else{
                j=next[j];
            }
        }
        if(j>=t.length){
            return (i-t.length);
        }else{
            return (-1);
        }
    }
     
     
     
     
    #include <iostream>
    #include "SqString.h"
     
    using namespace std;
     
    int main() {
        SqString s,t;
        int a,a1,i;
        ElemType e1,e2;
        
        InitIndex(s);
        InitIndex(t);
        
        cout<<"请输入主串个数:"<<endl; 
        cin>>a;
        for(i=0;i<a;i++){
            cout<<"请输入主串的元素:";
            cin>>e1;
            s.data[i]=e1;
        }
        s.length = a;
        
        for(i=0;i<a;i++){
            cout<<s.data[i]<<"  ";
     
        }
        cout<<endl;
        
        
        cout<<"请输入子串个数:"<<endl; 
        cin>>a1;
        for(i=0;i<a1;i++){
            cout<<"请输入子串的元素:";
            cin>>e2;
            t.data[i]=e2;
        }
        t.length = a1;
        for(i=0;i<a1;i++){
            cout<<t.data[i]<<"  ";
            
        }
        cout<<endl;
        
        cout<<"采用BF算法"<<endl;
        cout<<"第一个匹配的字符下标为:";
        int n = Index(s,t);
        if(n>=0)
            cout<<n;
        cout<<endl;
        
        cout<<"采用KMP算法"<<endl;
        cout<<"第一个匹配的字符下标为:";
        n = KMPIndex(s,t);
        if(n>=0)
            cout<<n<<endl;
        return 0;
    }
     
     
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(3条)

报告相同问题?

问题事件

  • 系统已结题 8月23日
  • 已采纳回答 8月15日
  • 创建了问题 8月15日

悬赏问题

  • ¥18 深度学习tensorflow1,ssdv1,coco数据集训练一个模型
  • ¥100 关于注册表摄像头和麦克风的问题
  • ¥30 代码本地运行正常,但是TOMCAT部署时闪退
  • ¥15 关于#python#的问题
  • ¥15 主机可以ping通路由器但是连不上网怎么办
  • ¥15 数据库一张以时间排好序的表中,找出多次相邻的那些行
  • ¥50 关于DynamoRIO处理多线程程序时候的问题
  • ¥15 kubeadm部署k8s出错
  • ¥15 Abaqus打不开cae文件怎么办?
  • ¥15 小程序准备上线,软件开发公司需要提供哪些资料给甲方