严蔚敏数据结构kmp算法详解

严蔚敏版数据结构所有算法代码------------------------线性数据结构-----------------------------2013年9月//线性表、链表//栈、队列//数组、广义表//串-------------------------线性表----------------------typedef struct{char name[20];//注意如果应用指针的形式//在初始化每个结点时一定要先为结点中的每个变量开辟内存空间char sex;char addr[100];unsigned int age;char phonenum[20];}node;//结点描述typedef struct{node *p;int length;//当前顺序表长度int listsize;//当前分配的线性表长度}list;//线性表描述list L;//定义一个线性表int initlist(list &l)//构造一个空的线性表{l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node));if(!(l.p))exit(1);l.length=0;l.listsize=LIST_INIT_SIZE;return true;}void destroylist(list &l)//销毁线性表操作{if(l.p!=NULL){free(l.p);printf("销毁成功!\n");}elseprintf("线性表不存在！\n");}int clearlist(list &l)//将线性表置空操作{if(l.p==NULL){printf("线性表不存在！\n");return false;}else{free(l.p);l.p=(node*)malloc(l.listsize*sizeof(node));l.length=0;}return true;}int listempty(list &l)//判断线性表是否为空表{if(l.p==NULL)return true;elsereturn false;}int getelem(list &l,int i,node &e)//用e返回表中第i个数据元素{if(l.p==NULL)return false;elsee=l.p[i-1];return true;}int priorelem(list &l,int i,node &pre_e)//得到第i个元素的前驱元素{if(i==0||l.p==NULL)return false;elsepre_e=l.p[i-1];return true;}int nextelem(list &l,int i,node &next_e)//得到表中第i个元素的后继元素{if(i>=l.length||l.p==NULL)return false;elsenext_e=l.p[i+1];return true;}int insertlist(list &l,int i,node &e)//将元素e插入到表l中第i个元素的后面{node *q,*k;if(i<1||i>l.length+1)return false;if(l.length>=l.listsize){l.p=(node*)realloc(l.p,(l.listsize+LISTINCREMENT)*sizeof(node));if(!l.p)exit(1);l.listsize+=LISTINCREMENT;}k=&l.p[i-1];for(q=&l.p[l.length-1];q>k;q--)*(q+1)=*q;*k=e;l.length++;return true;}int deletelist(list &l,int i,node &e)//删除表中第i个元素并用e返回其值{node *q;int j=i-1;if(i<1||i>l.length)return false;e=l.p[i-1];for(q=&l.p[i-1];j<l.length-1;j++)*q=*(++q);l.length--;return true;}void mergerlist(list la,list lb,list &lc)//归并两个按非递减排列的线性表{int la_len,lb_len,i=1,j=1,k=0;node ai,bj;la_len=la.length;lb_len=lb.length;while(i<=la_len&&j<=lb_len){getelem(la,i,ai);getelem(lb,j,bj);if(ai.a<=bj.a){insertlist(lc,++k,ai);i++;}else{insertlist(lc,++k,bj);j++;}}while(i<=la_len){getelem(la,i,ai);insertlist(lc,++k,ai);i++;}while(j<=lb_len){getelem(lb,j,bj);insertlist(lc,++k,bj);j++;}}int ListAscendingOrder(list &l)//按结点中某一元素的比较升序排列线性表中的结点{node e;int i,j;if(l.p==NULL||l.length==1)return ERROR;for(i=0;i<l.length-1;i++)for(j=i+1;j<l.length;j++)if(l.p[i].num>=l.p[j].num){e=l.p[i];l.p[i]=l.p[j];l.p[j]=e;}return OK;}//省略降序排列void MergerList(list la,list lb,list &lc)//将两线性表升序排列后再归并{node *q,*k,e1;int i=0,j=0,m=0,n;ListAscendingOrder(la);ListAscendingOrder(lb);printf("表a升序排列后为：\n");for(i=0;i<la.length;i++)printf("%d ",la.p[i].num);printf("\n");printf("表b升序排列后为：\n");for(i=0;i<lb.length;i++)printf("%d ",lb.p[i].num);printf("\n");i=0;while(i<la.length&&j<lb.length){if(la.p[i].num<=lb.p[j].num){e1=la.p[i];i++;}else{e1=lb.p[j];j++;}if(e1.num!=lc.p[lc.length-1].num)InsertList(lc,++m,e1);}if(i<la.length)while(i<la.length){if(la.p[i].num!=lc.p[lc.length-1].num)InsertList(lc,++m,la.p[i]);i++;}if(j<lb.length)while(j<lb.length){if(lb.p[j].num!=lc.p[lc.length-1].num)InsertList(lc,++m,lb.p[j]);j++;}printf("按升序排列再归并两表为：\n");for(n=0;n<lc.length;n++)printf("%d ",lc.p[n].num);printf("\n");}----------------------链表----------------------------- typedef struct{int num;}node;typedef struct LIST{node data;struct LIST *next;}list,*slist;int CreatList(slist &head)//此处应为只针对的引用{head=(list *)malloc(sizeof(list));if(!head)return ERROR;head->next=NULL;return OK;}void InvertedList(slist &head1,slist &head2){//构造新表逆置单链表函数list *p,*q;p=head1->next;q=p->next;if(p==NULL)printf("链表为空无法实现逆置操作\n");else{while(q!=NULL){p->next=head2->next;head2->next=p;p=q;q=q->next;}p->next=head2->next;head2->next=p;printf("逆置成功！?\n");}}void InsertList(slist &head,node &e)//此处应为指针的引用{//而不应该是list *headlist *p,*q;p=(list *)malloc(sizeof(list));q=head;while(q->next!=NULL)q=q->next;p->next=q->next;q->next=p;p->data=e;}void InvertedList(sqlist &head){//-------不构造新表逆置单链表函数---------// list *p,*q,*k;p=head->next;q=p->next;k=q->next;p->next=NULL;while(k!=NULL){q->next=p;p=q;q=k;k=k->next;}q->next=p;head->next=q;}//----交换链表中第i个和第j个结点，函数实现如下——// int SwapListNode(sqlist &head,int i,int j){int m,n,m1,n1,sum=0;list *p,*q,*k,*c,*d,*ba;ba=head->next;while(ba!=NULL){sum++;ba=ba->next;}if(i==j||i>sum||j>sum||i<1||j<1){printf("所要交换的两个结点有误！\n");return ERROR;}if(i<j){ m=i; n=j;}else{ m=j;n=i;}p=head;q=head;for(m1=1;m1<=m;m1++)p=p->next;for(n1=1;n1<=n;n1++)q=q->next;if(p->next==q){//如果结点相邻k=head;while(k->next!=p)k=k->next;//相邻两结点的交换p->next=q->next;q->next=p;k->next=q;}else{//如果结点不相邻k=head;c=head;while(k->next!=p)k=k->next;while(c->next!=q)c=c->next;d=p->next;//不相邻两结点之间的交换p->next=q->next;c->next=p;k->next=q;q->next=d;}return OK;}//-----将链表中结点按结点中某一项大小升序排列，函数实现如下-----// int AscendingList(sqlist &head){int m,n,sum=0,i,j;list *p,*q,*k;k=head->next;while(k!=NULL){sum++;k=k->next;}for(i=1;i<sum;i++)for(j=i+1;j<=sum;j++){p=head->next;m=1;while(m!=i){m++;p=p->next;}q=head->next;n=1;while(n!=j){n++;q=q->next;}if(p->data.exp>q->data.exp)//如果按exp降序排列，则应将>改为<；SwapListNode(head,i,j);}return OK;}//-----将两链表合并为一个链表------//int AddList(sqlist &head1,sqlist &head2,sqlist &head3){//已将表head1和表head2按某一项升序排列过sqlist p,q;node e;p=head1->next;q=head2->next;while(p!=NULL&&q!=NULL){if(p->data.exp<q->data.exp){InsertList(head3,p->data);p=p->next;}elseif(p->data.exp>q->data.exp){InsertList(head3,q->data);q=q->next;}elseif(p->data.exp==q->data.exp){e.coefficient=p->data.coefficient+q->data.coefficient;e.exp=p->data.exp;//e.exp=q->data.exp;InsertList(head3,e);p=p->next;q=q->next;}}if(p!=NULL)while(p!=NULL){InsertList(head3,p->data);p=p->next;}//如果p中有剩余，则直接将p中剩余元素插入head3中if(q!=NULL)while(q!=NULL){InsertList(head3,q->data);q=q->next;}//如果q中有剩余，则直接将q中的剩余元素插入head3中return 0;}-----------------------栈------------------------------//---------利用栈结构实现数制之间的转换------书3.2.1//typedef struct{int num;}node;typedef struct{node *base;node *top;int stacksize;}stack;//顺序栈结构定义int CreatStack(stack &stackll){stackll.base=(node *)malloc(INITSTACKSIZE*sizeof(node));if(!stackll.base)exit(OVERFLOW);stackll.top=stackll.base;stackll.stacksize=INITSTACKSIZE;return OK;}void push(stack &s,node e){//进栈操作if(s.top-s.base>=s.stacksize){ s.base=(node*)realloc(s.base,(s.stacksize+INCRESTACKMENT)*sizeof(node));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;//可以不写此语句；s.stacksize+=INCRESTACKMENT;}*(s.top++)=e;//*s.top++=e;}void pop(stack &s,node &e){//出栈操作if(s.top==s.base||s.base==NULL)printf("信息有误！\n");elsee=*--s.top;}//-------取栈顶元素函数------//void gettop(stack &s,node &e){if(s.base==s.top)printf("栈为空，无法取得栈顶元素！\n");else{e=*(s.top-1);}}//-----栈的应用：括号匹配的检验------书3.2.2////省略了大部分上述已有代码//int zypd(char c){//判断是否为左括号字符if(c=='['||c=='{'||c=='(')return OK;elsereturn ERROR;}int main(void){stack s;node e1,e2,e3;char st[INITSTACKSIZE];int i=0,j;CreatStack(s);printf("请输入括号字符，以'#'做结束符：");scanf("%c",&st[i]);while(st[i]!='#'){i++;scanf("%c",&st[i]);}if(!zypd(st[0]))printf("输入字符不合法！\n");else{for(j=0;j<i;j++){if(zypd(st[j])){//如果是左括号则将此字符压入栈中e1.c=st[j];push(s,e1);}else{//如果当前st[j]元素不是左括号//则取出栈顶元素，比较栈顶元素与当前st[j]元素是否项匹配//如果匹配，则栈顶元素出栈gettop(s,e2);if(e2.c=='['&&st[j]==']'||e2.c=='{'&&st[j]=='}'||e2.c=='('&&st[j] ==')')pop(s,e3);else{printf("括号验证失败！\n");break;}}}if(s.top==s.base)//当循环结束时，如果栈为空栈说明输入的括号合法printf("括号验证成功！\n");}getchar();system("pause");return 0;}//----------链栈描述---------//typedef struct Node{int num;struct Node *next;}node;typedef struct{Node *top;Node *base;}stack;void InitStack(stack &s){s.base=(Node *)malloc(sizeof(node));if(!s.base)exit(1);else{s.base->next=NULL;s.top=s.base;}}void InsertStack(stack &s,node e){node *p;p=(node *)malloc(sizeof(node));if(!p)exit(1);else{*p=e;p->next=s.top;s.top=p;}}void DeleteStack(stack &s,node &e){node *p;if(s.top==s.base)printf("栈为空！\n");else{p=s.top;s.top=s.top->next;e=*p;free(p);}}--------------------队列---------------------- //------链队列的描述及操作-------//typedef struct Node{int a;struct Node *next;}Qnode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue &Q){Q.front=(Qnode *)malloc(sizeof(Qnode));if(!Q.front)exit(1);Q.rear=Q.front;Q.front->next=NULL;}void InsertQueue(LinkQueue &Q,Qnode e){QueuePtr p;p=(Qnode *)malloc(sizeof(Qnode));if(!p)exit(1);*p=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}void DeleteQueue(LinkQueue &Q,Qnode &e){Qnode *p;if(Q.front==Q.rear)printf("队列为空！\n");else{p=Q.front->next;e=*p;Q.front->next=p->next;if(p==Q.rear)Q.rear=Q.front;free(p);}}//-------------循环队列---------------// typedef struct node{int data;struct node *next;}node;typedef struct queue{node *base;int front;int rear;}Queue;int tag;void InitQueue(Queue &Q){Q.base=(node *)malloc(MAX*sizeof(node));if(!Q.base)exit(1);Q.front=Q.rear=0;tag=0;}void InsertQueue(Queue &Q,node e){if(tag==1&&Q.front==Q.rear)printf("循环队列已满！\n");else{Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAX;if(Q.rear==Q.front)tag=1;}}void DeleteQueue(Queue &Q,node &e){if(tag==0&&Q.front==Q.rear)printf("队列为空！\n");else{e=Q.base[Q.front];Q.front=(Q.front+1)%MAX;if(Q.front==Q.rear)tag=0;}}int EmptyQueue(Queue &Q){if(Q.front==Q.rear&&tag==0)return 1;elsereturn 0;}--------------------------串----------------------------------- //-----------串：堆分配存储形式的一些操作------------------// typedef struct string{char *ch;int length;}sstring;void CreatString(sstring &T){T.ch=(char*)malloc(sizeof(char));T.length=0;}void StringAssign(sstring &T,char *s){//将串s的值赋值给串Tif(T.ch)free(T.ch);T.ch=(char*)malloc(strlen(s)*sizeof(char));//或者T.ch=(char*)malloc(sizeof(char));//动态开辟空间不同于静态内存开辟之处if(!T.ch){printf("ERROR");exit(1);}strcpy(T.ch,s);T.length=strlen(s);}void ClearString(sstring &T){if(T.ch)free(T.ch);T.length=0;}void ConcatString(sstring &T,sstring s1,sstring s2){//串连接if(T.ch)free(T.ch);T.ch=(char*)malloc((strlen(s1.ch)+strlen(s2.ch))*sizeof(char));if(!T.ch){printf("ERROR\n");exit(1);}strcpy(T.ch,s1.ch);strcat(T.ch,s2.ch);T.length=strlen(s1.ch)+strlen(s2.ch);}void SubString(sstring &sub,sstring s,int pos,int len){//取子串操作，取串s中位置从pos至len处的子串于sub中int i,j=0;if(sub.ch)free(sub.ch);sub.ch=(char *)malloc((len-pos+1+1)*sizeof(char));if(!sub.ch){printf("ERROR\n");exit(1);}for(i=pos-1;i<len;i++)sub.ch[j++]=s.ch[i];sub.ch[j]='\0';sub.length=strlen(sub.ch);}int CountString(sstring s1,sstring s2){//判断子串s2在母串s1中出现的次数int i,j,k,count=0;if(s1.length==0||s2.length==0||s2.length>s1.length){printf("ERROR\n");return 0;}else{for(i=0;i<s1.length;i++){k=1;for(j=0;j<s2.length;j++){if(s2.ch[j]!=s1.ch[i+j]){k=0;break;}}if(k)count++;}}return count;}void Deletestring(sstring &s,int pos,int len) {//删除s串中位置从pos到len处的元素int i,j,k;if(s.length==0)printf("ERROR\n");else{for(i=pos-1,j=len;j<s.length;i++,j++) s.ch[i]=s.ch[j];s.ch[i]='\0';s.length-=(len-pos)+1;}}void DeleteSub(sstring &s1,sstring s2){//删除母串s1中的子串s2int i,j,k,tag=0;for(i=0;i<s1.length;i++){k=1;if(tag)i--;for(j=0;j<s2.length;j++)if(s2.ch[j]!=s1.ch[i+j]){k=0;break;}if(k){Deletestring(s1,i+1,i+s2.length);tag=1;}}}----------------KMP算法----------------int index_kmp(string T,string S,int pos){int i=pos,j=1;while(i<=S.length&&j<=T.length){if(S.ch[i]==T.ch[j]){i++;j++;}elsej=next[j+1];}if(j>T.length)return i-T.length;elsereturn 0;}void get_next(string T){int i=1,j=0;next[1]=0;while(i<=T.length){if(j-1==0||T.ch[i]==T.ch[j]){i++;j++;if(T.ch[i]!=T.ch[j])next[i]=j;elsenext[i]=next[j];}elsej=next[j];}}———————----------------数组——————————————-----------矩阵转置的经典算法---------for(i=0;i<row;i++)for(j=0;j<col;j++)b[j][i]=a[i][j];时间复杂度为O（row*col),每个元素都要存储，相对于稀疏矩阵来说比较浪费存储空间。

数据结构——KMP算法算法介绍 KMP算法是⼀种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此⼈们称它为克努特—莫⾥斯—普拉特操作（简称KMP算法）。

KMP算法的核⼼是利⽤匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的⽬的。

具体实现就是通过⼀个next()函数实现，函数本⾝包含了模式串的局部匹配信息。

KMP算法的时间复杂度O(m+n)。

next数组 我们记主串为字符串S，模式串为字符串P。

我们⽤next[j]表⽰以字符Pj结尾的⼦串的长度相等的前缀字符串与后缀字符串长度的最⼤值。

特别地，当没有满⾜条件的⼦串时，next[j] = 0。

为了⽅便起见，我们将字符串从下标1开始匹配。

如此，next数组所表⽰的长度就与下标数值相等了。

算法思路 我们从左到右依次枚举S的每⼀个字符Si，对于当前待匹配字符Si，我们假设当前P字符串中已匹配到Pj。

那么我们只需判断Si和Pj+1，若两者相同，则继续匹配。

若两者不相同，那么我们使j=next[j]，即可最⼤限度的减少匹配次数。

因为S字符串的从某位置开始到前i-1的部分与P字符串的前j个字符已匹配(即完全相同)，如图中两蓝⾊直线所夹的S、P的两段，⽽P1到Pnext[j]部分是长度最⼤的与以Pj结尾的后缀完全相同的前缀（图中绿⾊线段），⽽该以Pj结尾的后缀则必定与S中⼀段以Si-1结尾的⼦串完全相同，因⽽保证了上述操作的正确性。

接下去只需重复上述操作即可。

⽽对于next数组的预处理，也同上述操作类似，我们只需要以字符串P来匹配字符串P即可。

模板呈现 模板题链接： 代码如下：#include <iostream>#include <algorithm>#include <cstdio>using namespace std;const int M = 1e5+10;int n,m;int ne[M];char s[M],p[M];int main(){cin>>n>>p+1;cin>>m>>s+1;for(int i=2,j=0;i<=n;i++){while(j && p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}for(int i=1,j=0;i<=m;i++){while(j && s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==n){printf("%d ",i-n+1-1);j=ne[j]; //可有可⽆，好习惯要加上。

KMP算法详解我们从一个普通的串的模式匹配算法开始讲起，这样你才能更深入的了解KMP算法及其优点。

咱们先来看看普通的串的模式匹配算法是怎么进行比较的主串（S） a b a b c a b c a c b a b子串（T）a b c a c （子串又被称为模式串）红色表示当前这趟比较指针所在位置，兰色表示当前这趟比较中匹配的部分第一趟（详细过程）a b a b c a b c a c b a ba b c a ca b a b c a b c a c b a ba b c a ca b a b c a b c a c b a ba b c a c遇到不匹配的地方时指针回朔，子串向前移动一位（下同），变成如下形式a b a b c a b c a c b a ba b c a c第二趟（省略了中间阶段指针移动比较过程，下同）a b a b c a b c a c b a ba b c a c第三趟a b a b c a b c a c b a ba b c a c第四趟a b a b c a b c a c b a ba b c a c第五趟aba b c a b c a c b a ba b c a c第六趟ab a b c a b c a c b a ba b c a c_完成匹配，跳出这就是普通算法的详细匹配过程，看明白了算法就简单了详细算法我现在就不给了，等以后有时间再编辑。

不过假如串的长度为m,子串的长度为n 的话，那么这个算法在最坏的情况下的时间复杂度为O(m*n) ,有没有办法降低它的时间复杂度呢？（废话，当然有拉，不然回这个帖子干什么）拜D.E.K nuth 和J.H.M orris 和V.R.P ratt 所赐，我们有了一种时间复杂度为O(m+n)的算法，为了纪念这3位强人为计算机科学所做的贡献，分别取这3位先生的名字的首写字母K，M，P来命名这个算法，即著名的KMP算法。

我们先不管这个KMP算法是什么，我们先来看看我们能够想到怎样的方法来改进上面的普通算法。

数据结构kmp算法详解
KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。

KMP 算法的时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。

理解KMP算法的关键是要理解它使用的“部分匹配表”（partial match table），该表可以在O(n)的时间内预处理出来，用于帮助寻找匹配失败时应该跳转到的下一个位置。

相比于暴力匹配算法，KMP算法在遇到不匹配的字符时，不会同时回退txt和pat的指针，而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配，因此不会重复扫描txt，时间复杂度只需O(N)。

KMP算法的难点在于，如何计算 dp 数组中的信息以及如何根据这些信息正确地移动pat 的指针，这需要确定有限状态自动机来辅助。

串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版习题集解析部分第4章串——《数据结构题集》-严蔚敏.吴伟民版源码使⽤说明链接☛☛☛课本源码合辑链接☛☛☛习题集全解析链接☛☛☛相关测试数据下载链接☛本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼04 串⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04源码测试数据存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04\Data⼀、基础知识题4.1❶简述空串和空格串（或称空格符串）的区别。

4.2❷对于教科书4.1节中所述串的各个基本操作，讨论是否可由其他基本操作构造⽽得，如何构造？4.3❶设s = ‘I AM A STUDENT’，t = ‘GOOD’，q = ‘WORKER’。

求：StrLength(s)，StrLength(t)，SubString(s, 8, 7)，SubString(t, 2, 1)，Index(s, ‘A’)，Index(s, t)，Replace(s, ‘STUDENT’, q)，Concat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8)))。

4.4❶已知下列字符串a = ‘THIS’,　f = ‘A SAMPLE’,　c = ‘GOOD’,　d = ‘NE’,b = ‘ ’.s = Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))),t = Replace(f, SubString(f, 3, 6), c),u = Concat(SubString(c, 3, 1), d),g = ‘IS’,v = Concat(s, Concat(b, Concat(t, Concat(b, u)))),试问：s，t，v，StrLength(s)，Index(v, g)，Index(u, g)各是什么？4.5❶试问执⾏以下函数会产⽣怎样的输出结果？void demonstrate(){StrAssign(s, ‘THIS IS A BOOK’);Replace(s, SubString(s, 3, 7), ‘ESE ARE’);StrAssign(t, Concat(s, ‘S’));StrAssign(u, ‘XYXYXYXYXYXY’);StrAssign(v, SubString(u, 6, 3));StrAssign(w, ‘W’);printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));}//demonstrate4.6❷已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。

KMP算法详解KMP 算法详解KMP 算法是⼀个⼗分⾼效的字符串查找算法，⽬的是在⼀个字符串 s 中，查询 s 是否包含⼦字符串 p，若包含，则返回 p 在 s 中起点的下标。

KMP 算法全称为 Knuth-Morris-Pratt 算法，由 Knuth 和 Pratt 在1974年构思，同年 Morris 也独⽴地设计出该算法，最终由三⼈于1977年联合发表。

举⼀个简单的例⼦，在字符串 s = ababcabababca 中查找⼦字符串 p = abababca，如果暴⼒查找，我们会遍历 s 中的每⼀个字符，若 s[i] = p[0]，则向后查询p.length() 位是否都相等。

这种朴素的暴⼒的算法复杂度为O(m×n)，其中m和n分别是 p 和 s 的长度。

KMP 算法可以⽅便地简化这⼀查询的时间复杂度，达到O(m+n)。

1. PMT 序列PMT 序列是 KMP 算法的核⼼，即 Partial Match Table（部分匹配表）。

举个例⼦：char a b a b a b c aindex01234567PMT00123401PMT 的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

PMT[0] = 0: 字符串 a 既没有前缀，也没有后缀；PMT[1] = 0: 字符串 ab 前缀集合为 {a}，后缀集合为 {b}，没有交集；PMT[2] = 1: 字符串 aba 前缀集合为 {a, ab}，后缀集合为 {ba, a}，交集为 {a}，交集元素的最长长度为1；PMT[3] = 2: 字符串 abab 前缀集合为 {a, ab, aba}，后缀集合为 {bab, ab, b}，交集为 {ab}，交集元素的最长长度为2；…… 以此类推。

2. 算法主体现在我们已经知道了 PMT 序列的含义，那么假设在 PMT 序列已经给定的情况下，如何加速字符串匹配算法？tar 存储 s 的下标，从 0 开始，若 tar > s.length() - 1，代表匹配失败；pos 存储 p 的下标，从 0 开始，若 s[tar] != p[pos]，则 pos ⾛到下⼀个可能匹配的位置。

数据结构教学中KMP算法解析摘要：模式匹配是字符串的基本运算之一，也是数据结构教学中的难点之一。

分析了模式匹配KMP算法以及算法中next函数的含义，给出了next函数的两种实现方法，有助于在教学实践中帮助学生更好地理解该算法。

关键词：数据结构；模式匹配；KMP算法0引言模式匹配（Patten Matching）是许多计算机应用领域的基础问题，在数据结构中模式匹配是字符串的基本运算之一。

字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。

有两个字符串S和T，字符串S称为目标串，字符串T称为模式串，要求找出模式T在S中的首次出现的位置。

一旦模式T在目标S中找到，就称发生一次匹配。

有些应用可能会要求找出所有的匹配位置^[1]。

例如，目标串S= 'Shanghai'，模式串T= 'gha'，则匹配结果为4。

模式匹配的典型算法包括朴素匹配算法、KMP算法和BM算法等，其中KMP算法是效率较高且经典的模式匹配算法之一^[2]。

在数据结构教学中，由于KMP算法较难理解，课堂讲授往往很难取得好的效果。

本文通过对传统的朴素匹配算法与KMP算法的比较，分析next函数的含义以及实现方法，来帮助理解KMP算法。

1朴素匹配算法在朴素匹配算法中，S和T分别为目标串和模式串，变量i和j 为两个静态指针，分别表示S和T中当前正待比较的字符位置。

算法的基本思想是：第1趟匹配：从S的第1个字符（序号为0）起和T的第一个字符比较之，如果相等，则继续逐个比较后续字符（i++；j++），否则开始下一趟匹配。

新的一趟匹配：i的初值为上一趟的初值+1 ，j的初值为1，如果比较结果相等，则继续逐个比较后续字符，否则开始下一趟匹配。

依次类推，直至某一趟匹配中，T的每个字符依次和S中的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。