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

Question

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

Answer 1

#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串：一个结构体中：一个数组存储字符串，一个整型存储长度