模式串匹配算法，由之前的朴素模式算法延伸到KMP算法，效率上提升了将近一半。朴素模式算法上是将主串中的字符与子串中的字符一一比较，然后让子串的字符不匹配的字符重新在从主串匹配完的部分匹配。这样会导致一个问题就是子串不断地回溯比较，效率低下。因而KMP算法诞生，就是改进了这一个问题。KMP算法是当匹配到不相同的字符时，将匹配下一个字符的位置交给了next数组。next数组的原理是最大字符前缀和最大字符后缀相等长度加一。大大的提高了效率。但是尽管KMP算法提高了效率，仍然有无意义的比较。因而改进KMP算法的next数组为nextval数组，从左到右依次比较是否与之前的字符相同，若相同则将相同的next值赋值到相同的字符中，这样就大大的节省了无意义的比较次数。
下面看详细代码：
#include <iostream>#include <stdio.h>#include <stdlib.h>#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){ S.ch = (char*)malloc(MaxSize*sizeof(char)); S.length = 0;} //求子串bool SubString(SString &Sub,SString S,int pos,int len){ //子串越界 if(pos+len-1>S.length){ return false; } for(int i=pos;i<pos+len;i++){ Sub.ch[i-pos+1] = S.ch[i]; } Sub.length = len; return true;}//朴素模式匹配算法 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; }}//求模式串中next数组void get_next(SString T,int next[]){ int i = 0; int 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]; } }} //KMP算法2 int IndexKMP(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; }}//KMP算法1int Index(SString S,SString T,int next[]){ int i=k,j=1; 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; }} int main(int argc, char** argv) { HString S; InitHString(S); return 0;}