(27)王道数据结构-KMP算法

引入原因

朴素模式匹配算法中，当某些子串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加

实现代码

#include<stdio.h>
#include<string.h>
#define MAXLEN 255  //预定义最大串长为255
typedef struct {    
    char ch[MAXLEN];//每个分量存储一个字符
    int length;     //串的实际长度
}SString;
bool StrAssing(SString *T, char ch[]);
bool SubString(SString *sub, SString S, int pos, int len);
int StrCompare(SString S, SString T);
int StrLength(SString T);
int Index(SString S, SString T);
void get_next(SString T, int next[]);
int main(void) {
    SString S, sub;
    char ch[] = "This is String Demo Code";
    StrAssing(&S, ch);
    SubString(&sub, S, 2, 5);
    
    int index = Index(S, sub);
    printf("index=%d\n", index);
    return 0;
}

//赋值操作
bool StrAssing(SString *T, char str[]) {
    //清空原始内容
    memset(T->ch, 0, MAXLEN);
    T->length = 0;
    //重新赋值为chars
    strcpy(T->ch, str);
    T->length = (int)strlen(str);
    printf("len=%d\n",strlen(T->ch));
}

//求子串
bool SubString(SString *sub, SString S, int pos, int len) {
    //子串范围越界
    if (pos + len - 1 > S.length) {
        return false;
    }
    //清空T中的原始内容
    memset(sub->ch, 0, MAXLEN);
    sub->length = 0;
    strncpy(sub->ch, S.ch + pos, len);
    //重新设置串的长度
    sub->length=len;
    return true;
}

//比较操作
int StrCompare(SString S, SString T) {
    for (int i = 1; i <= S.length && i <= T.length; i++) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
    }
    return S.length - T.length;
}

//朴素模式匹配算法
int Index(SString S, SString T) {
    int i = 1, j = 1;
    int next[T.length + 1];
    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;
    }
}

//求模式串T的next数组
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;
            //若pi=pj，则next[j+1]=next[j] + 1
            next[i] = j;
        } else {
            //否则令j = next[j],循环继续
            j = next[j];
        }
    }
}

//获取字符串长度
int StrLength(SString T) {
    return T.length;
}