weixin_52431982 2021-04-23 20:41 采纳率: 50%
浏览 54
已采纳

kmp函数代码填空 字符串匹配

#include <stdio.h>
#include <malloc.h>
#define N 100
#include<string.h>
int lengthStr(char str[])
{
    int i;
    int len;
    len = 0;
    i = 0;
    while (str[i] != '\0')
    {
        i ++;
    }
    len = i;
    return len;
}
int strMatchBF(char mainStr[], char subStr[])
{
    // 穷举法进行字符串匹配
    // 返回子串subStr与主串mainStr相匹配的第一个位置
    int  lenMS,lenSS;
    int i,j;
    int isOK;
    lenMS = lengthStr(mainStr); // 计算主串的长度
    lenSS = lengthStr(subStr); // 计算子串(模式串)的长度
    i = 0;
    isOK = 0;
    while (i<lenMS){
        isOK = 1;
        for (j = 0; j < lenSS; ++j) {
            if(subStr[j] != mainStr[i+j] )
            {
                isOK = 0;
                break;
            }
        }
        if (!isOK)
            i++;
        else
            return i;     // 匹配成果,返回相匹配的第一个字符的位置
    }
    return -1;   // 匹配不成功,返回-1
}

void copyStrTo(char str[],char strcopy[],int startp,int endp)
{
    int i;
    int j;
    // 清空 strcopy 字符串
    j = lengthStr(strcopy);
    for (i = 0;i<j;i++){
        strcopy[i] = '\0';
    }
    if (startp > endp) return ;
    for(i = startp,j=0;i<=endp;i++,j++){
        strcopy[j] = str[i];
    }
}

int isEqual(char s1[], char s2[])
{
    // 判断两个字符串是否相等
    int len1,len2;
    int i;
    len1 = lengthStr(s1);
    len2 = lengthStr(s2);
    if (len1 != len2)
    {
        return 0;
    }
    for (i=0;i<len1;i++){
        if (s1[i] != s2[i])
            return 0;
    }
    return 1;
}
int computePrefixLen(char str[],int startp,int endp)
{
    // 计算字符串str的最大相等前缀后缀长度
    char *s1, *s2;
    int len;
    int i;

    if(startp == endp) return 0;
    s1 = (char*)malloc(sizeof (char) * (endp - startp+1));
    s2 = (char*)malloc(sizeof (char) * (endp - startp+1));

    i = 1;
    do {
        copyStrTo(str,s1,startp,endp-i);
        copyStrTo(str,s2,startp+i,endp);
        if (isEqual(s1,s2))
            return lengthStr(s1);
        else
            i = i+1;
    } while (startp <= endp-i);
    return 0;
}
void computeNext(char str[], int next[])
{
    // 计算字符串的next数组
    int i,j;
    int len;
    int preLen;
    len = lengthStr(str);
    // 初始化 next 数组
    for (i = 0; i < len; ++i) {
        next[i] = -2;
    }
    // 将所有与 str[0] 相等的字符的位置设置为 -1
    for (i = 0; i < len; ++i){
        if (str[i] == str[0])
            next[i] = -1;
    }
    // 对于 next[i]==-2的位置,计算匹配失败时,下一个需要匹配的位置,使用相等最大前缀和后缀
    for (i = 0; i < len; ++i){
        if (next[i] == -2){
            preLen = computePrefixLen(str,0,i);  // 计算字符串str[0]-str[i]的最大相等前缀后缀长度
            next[i] = preLen;
        }
    }

}
int strMatchKMP(char mainStr[], char subStr[])
{
    // KMP法进行字符串匹配
    // 返回子串subStr与主串mainStr相匹配的第一个位置

    int * next;
    int lenSS,lenMS;
    int i,j;
    lenSS = lengthStr(subStr);
    next = (int *)malloc(sizeof (int ) * lenSS);
    computeNext(subStr,next);
    lenMS = lengthStr(mainStr);
    i = 0;
    j = 0;
    while (i<lenMS-lenSS+1){
        while (j<lenSS)
        {
            if (mainStr[i] == subStr[j]){
                i++;
                j++;
            } else{
                j = next[j];
                if (j == -1) {j = 0;i = i+1;}
            }
        }
        return i-j;
    }
    return -1;
}
int searchAllMatchingStr(char mainS[],char subS[],int pos[])
{
   



    // 编写代码来搜索主串 mainS 中所有与子串 subS 相匹配的位置,将每个匹配串的起始位置存入 pos中。
    // 同时,返回主串 mainS 中与子串 subS相匹配的个数


    return 0;
}
void fuzzyMatching(char mainS[], char subS[], int pos[])
{
    // 模糊匹配,搜索在主串 mainS 中,与子串 subS中,'*'符号前后两个字符串相匹配的位置,将与'*'符号前面字符串相匹配的
    // 字符串的第一个位置存储 pos[0] 中,与'*'符号后面字符串相匹配的最后一个位置存储 pos[1]中。

}
int main() {
    char mainS[30] = {'a','r','b','c','d','p','w','d','p','a','r','p','d','p','w','a','o','d','p','w','d','p','a','y'};
    char subS[10] = {'d','p','w','d','p','a'};
    char subS2[10] = {'p','a','*','p','a'};
    int pos[10];
    int matchLen;
    matchLen = searchAllMatchingStr(mainS,subS,pos);
    for (int i = 0; i < matchLen; ++i) {
        printf("\n matching is ok. the %d substring position is %d",i,pos[i]);
    }

    fuzzyMatching(mainS,subS2,pos);
    printf("\n matching is ok. the start position is %d, and the last position is %d",pos[0],pos[1]);

    return 0;
}
  • 写回答

5条回答 默认 最新

  • 正在学C++ 2021-04-23 21:27
    关注
    #include<stdio.h>
    #define MAXSTRLEN 20
    typedef struct SString {
        int leng;
        char data[MAXSTRLEN+1];   //第一个位置不使用
    }SString;
    
    void InitSString(SString &S, int le){
        printf("Init(%d): ",le);
        S.leng = le;
        for(int i=1;i<=S.leng;i++) scanf("%c",&S.data[i]);
        getchar();
    }
    
    //简单模式匹配
    int Index(SString S, SString T, int pos){
        //返回  模式串T  在主串S中第pos个字符之后 的位置。如果不存在,返回0
        //T非空  1<=pos<=S.leng
        int i=pos, j=1;
        while(i<=S.leng && j<=T.leng){
            if(S.data[i]==T.data[j]) {i++;j++;}
            else{i = i-j+2; j=1;}
        }
        if(j>T.leng) return i-T.leng;
        else return 0;
    }
    
    
    //KMP算法
    int Index_KMP(SString S, SString T, int pos, int next[]){
        //T非空,1<=pos<=S.leng
        int i=pos,j=1;
        while(i<=S.leng && j<=T.leng)
            if(j==0||S.data[i]==T.data[j]) {i++;j++;}
            else j = next[j];
        if(j>T.leng) return i-T.leng;
        else return 0;
    }
    //next的计算方法
    void get_next(SString T, int next[]){
        int i=1,j=0;
        next[1]=0;
        while(i<T.leng)
            if(j==0 || T.data[i]==T.data[j]) {i++;j++;next[i]=j;}
            else j = next[j];
    }
    //next的计算方法的修正
    void get_nextval(SString T, int *nextval){
        int i=1,j=0;
        nextval[1]=0;
        while(i<T.leng)
            if(j==0 || T.data[i]==T.data[j]) {
                i++;j++;
                if(T.data[i]!=T.data[j]) nextval[i]=j;
                else nextval[i] = nextval[j];
            }
            else j = nextval[j];
    }
    int main(){
        SString S,T;
        InitSString(S,10);
        InitSString(T,5);
        printf("Easy_Index:%d\n",Index(S,T,1));
    
        int next[T.leng+1];
        get_nextval(T,next);
        printf("KMP_next:%d\n",Index_KMP(S,T,1,next));
    
        get_next(T,next);
        printf("KMP_nextval:%d\n",Index_KMP(S,T,1,next));
    
        return 1;
    }

    C语言描述简单模式匹配和KMP算法。

    定长顺序存储SString串:一个结构体中:一个数组存储字符串,一个整型存储长度

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

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