(26)王道数据结构-串的朴素匹配

匹配模式

串的匹配模式: 在主串中找到与模式串相同的子串，并返回其所在的位置

模式匹配

若主串S中存在与串T相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0。只要有一个字符不同，就可以停止检查当前子串

朴素模式匹配算法

代码一:

#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);
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 k = 1;
    int i = k, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            ++i;
            ++j;    //继续比较后继字符
        } else {
            k++;    //检查下一个字符
            i = k;
            j = 1;
        }
    }
    if (j > T.length) {
        return k;
    } else {
        return 0;
    }
}

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

代码二:

#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);
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;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            ++i;    //继续比较后继字符
            ++j;
        } else {
            i = i - j + 2;
            j = 1;  //指针后退重新开始匹配
        }
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0;
    }
}

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

性能分析

较好情况下，每一个子串第一个字符就与模式串不匹配
时间复杂度:
若模式串长度为m, 主串长度为n, 最多需要(n-m+1)*m次 比较则:
匹配成功的最好时间复杂度: O(m)
匹配失败的最好时间复杂度: O(n-m+1) = O(n-m)≈O(n)
匹配失败最坏时间复杂度: 每个子串的前m-1个字符都与模式串匹配,只有第m个串不匹配最坏时间复杂度: O(mn)