串的顺序表示和匹配（C语言）

#include <stdio.h>
#include <stdlib.h>

const int MAXSIZE = 100;
#define OK 1;
#define ERROR 0;
#define OVERFLOW 0;

typedef int Status;

typedef struct {
    char *ch;
    int length;
}SqString;

//串的初始化
Status InitStr(SqString *str){
    str->ch=(char*)malloc(sizeof(char)*(MAXSIZE+1));
    str->length=0;
    if(!str->ch) return OVERFLOW;  //分配失败 
    return OK;
}

//串赋值
Status StrAssign(SqString *str,char arrChar[],int len){
    int i;
    for(i=1;i<=len;i++){
        str->ch[i]=arrChar[i-1];  //ch[0]空置 
    }
    str->length=len;
    return OK;
}

//串打印 
Status StrPrint(SqString str){
    int i;
    for(i=1;i<=str.length;i++){
        printf("%c",str.ch[i]);
    }
    printf("\n");
    return OK;
}


//串匹配BF算法
int IndexOf_BF(SqString mainStr,SqString subStr){
    int i=1,j=1;
    while(i<=mainStr.length&&j<=subStr.length){
        if(mainStr.ch[i]==subStr.ch[j]) {
            i++;
            j++;
        } else {
            i=i-j+2;  //主串指针回溯到下一轮匹配的第一个字符
            j=1;  //子串指针回溯到1号字符 
        }
    }
    if(j==subStr.length+1) return i-subStr.length;
    return 0;
}


//串匹配KMP算法 
int IndexOf_KMP(SqString mainStr,SqString subStr,int next[]){
    int i=1,j=1;
    while(i<=mainStr.length&&j<=subStr.length){
        if(j==0||mainStr.ch[i]==subStr.ch[j]){
            i++;
            j++;
        } else {
            j=next[j];
        }
    }
    if(j==subStr.length+1) return i-subStr.length;
    return 0;
}
Status get_next(SqString subStr,int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<subStr.length){
        if(j==0||subStr.ch[i]==subStr.ch[j]){
            i++;
            j++;
            next[i]=j;
        } else {
            j=next[j];
        }
    }
    return OK;
}

//动态分配int型数组的空间，通过实参返回地址 
Status DynamicAllocationArr(int **arr,int size){
    (*arr)=(int*)malloc(sizeof(int)*size);
    if(!(*arr)) return OVERFLOW;
    return OK; 
}

//动态分配int型数组的空间，通过函数返回值返回地址 
int* DynamicAllocationArr2(int *arr,int size){
    arr=(int*)malloc(sizeof(int)*size);
    if(!arr) return OVERFLOW;
    return arr; 
}


int main(void){
    SqString str1;
    
    //初始化 
    Status initStrResult = InitStr(&str1);
    printf("串str1初始化结果码：%d\n",initStrResult);
    
    //串赋值
    char arrChar[]={‘h‘,‘e‘,‘l‘,‘l‘,‘o‘,‘w‘,‘ ‘,‘w‘,‘o‘,‘r‘,‘l‘,‘d‘,‘!‘};
    int arrLen=sizeof(arrChar)/sizeof(arrChar[0]);
    Status assignStrResult = StrAssign(&str1,arrChar,arrLen);
    printf("串str1赋值结果码：%d\n",assignStrResult);
    printf("主串：");
    StrPrint(str1); 
    
    //朴素匹配 
    SqString str2;  //作为子串(模式串)
    InitStr(&str2);
    char arrChar2[]={‘r‘,‘l‘,‘d‘};
    StrAssign(&str2,arrChar2,sizeof(arrChar2)/sizeof(arrChar2[0]));  //生成有数据的串 
    printf("模式串(子串)：");
    StrPrint(str2); 
    int index1=IndexOf_BF(str1,str2);
    if(index1){
        printf("BF-匹配结果地址：%d\n",index1);
    } else {
        printf("匹配失败\n");
    }
    
    //KMP匹配 
    int *next=DynamicAllocationArr2(next,str2.length+1);  //动态分配数组空间 
    get_next(str2,next);  //生成部分匹配表
    int index2=IndexOf_KMP(str1,str2,next);
    if(index2){
        printf("KMP-匹配结果地址：%d\n",index2);
    } else {
        printf("匹配失败\n");
    }
    
    printf("\nEND");
    return 0;
}