2023年7月20日发(作者：)

朴素匹配算法C语⾔,模式串匹配算法（朴素模式匹配算法和KMP算法）模式串匹配算法，由之前的朴素模式算法延伸到KMP算法，效率上提升了将近⼀半。朴素模式算法上是将主串中的字符与⼦串中的字符⼀⼀⽐较，然后让⼦串的字符不匹配的字符重新在从主串匹配完的部分匹配。这样会导致⼀个问题就是⼦串不断地回溯⽐较，效率低下。因⽽KMP算法诞⽣，就是改进了这⼀个问题。KMP算法是当匹配到不相同的字符时，将匹配下⼀个字符的位置交给了next数组。next数组的原理是最⼤字符前缀和最⼤字符后缀相等长度加⼀。⼤⼤的提⾼了效率。但是尽管KMP算法提⾼了效率，仍然有⽆意义的⽐较。因⽽改进KMP算法的next数组为nextval数组，从左到右依次⽐较是否与之前的字符相同，若相同则将相同的next值赋值到相同的字符中，这样就⼤⼤的节省了⽆意义的⽐较次数。下⾯看详细代码：#include#include#include#define MaxSize 255/* run this program using the console pauser or add your own getch, system("pause") or input loop *//**串的顺序存储和链式存储由于C语⾔中有对串直接操作的函数,这只列举⼀种操作朴素模式匹配算法*///静态定义串的结构体(定长顺序存储)typedef struct{char ch[MaxSize];//存储字符的数组int length;//串的实际长度}SString;//动态⽅式定义串的结构体(为了避免存储密度低的问题,让结点存储多个字符)typedef struct StringNode{char ch[4];//每个结点放四个字符struct StringNode *next;//指针域}StringNode,*String;//动态定义串的结构体(堆分配存储)typedef struct{char *ch;//按照串长分配储存区,ch指向串的⾸地址int length;//串的实际长度}HString;//堆分配初始化void InitHString(HString &S){ = (char*)malloc(MaxSize*sizeof(char)); = 0;}//求⼦串bool SubString(SString &Sub,SString S,int pos,int len){//⼦串越界if(pos+len-1>){return false;}for(int i=pos;[i-pos+1] = [i];} = len;return true;}//朴素模式匹配算法int Index(SString S,SString T){int k=1;int i=k,j=1;while(i<= && j<=){if([i]==[j]){++i;++j;//继续⽐较后续字符}else{k++;//检查下⼀个⼦串i=k;j=1;}}if(j>){return k;}else{return 0;}}//求模式串中next数组void get_next(SString T,int next[]){int i = 0;int j = 0;next[1] = 0;while(iif(j==0||[i]==[j]){++i;++j;//若pi=pj,则next[j+1]=next[j]+1next[i] = j;}else{//否则循环继续j = next[j];}}}//KMP算法2int IndexKMP(SString S,SString T){int i=1,j=1;int next[+1];get_next(T,next);while(i<= && j<=){if(j==0||[i]==[j]){++i;++j;//继续⽐较后续字符}else{j=next[j];//模式串向右移动}}if(j>){return ;//匹配成功}else{return 0;}}//KMP算法1int Index(SString S,SString T,int next[]){int i=k,j=1;while(i<= && j<=){if(j==0 || [i]==[j]){++i;++j;//继续⽐较后续字符}else{j=next[j];}}if(j>){return ;}else{return 0;}}int main(int argc, char** argv) {HString S;InitHString(S);return 0;}