串的朴素模式匹配算法

一定是主串中存在的才叫“子串”

模式串：想尝试在主串中找到的串，未必存在

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置【就是定位操作】

朴素模式匹配算法：

【比较好的情况：每个子串的第一个字符就与模式串不匹配，若模式串长度为m，主串长度为n，则匹配成功的最好时间复杂度：O(m)，匹配失败的最好时间复杂度：O(n-m+1)=O(n-m)=O(n)】

【若模式串长度为m，主串长度为n，则直接匹配成功/匹配失败最多需要(n-m+1)*m次比较，最坏时间复杂度：O(nm)，这种情况就是每个子串的前m-1个字符都和模式串匹配，只有第m个字符不匹配，所以指针需要回溯重新来匹配】

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

#define MAXIEN 255  //预定义最大串长为255

typedef struct{
    char ch[MAXIEN];  //每个分量存储一个字符
    int length;  //串的实际长度
}SString;

//只要有一个字符不同，就可以停止检查当前子串，所有对应位置的字符都相同，则匹配成功，返回k
int Index(SString *S,SString *T){
    int k=1;  //k记录当前检查的子串起始位置
    int i=k,j=1;
    while(i<=S->length && j<=S->length){
        if(S->ch[i] == T->ch[i]){
            ++i;
            ++j;  //继续比较后继字符
        }
        else{
            k++;  //检查下一个子串
            i=k;
            j=1;
        }
    }
    if(j<T->length){
        return k;
    }else{
        return 0;
    }
}

int main(){
    SString S;
}