下载文档原格式
字符串的模式匹配前⾔：记得⼤⼆学习字符串匹配也只是把书上的伪代码看懂，原理搞明⽩，也就没有亲⾃去实现代码，⽽且⾃⼰也不是搞算法的，所以偶尔做题也很少遇到字符串匹配题，上次考试很尴尬遇到了这种题，虽然知道考的啥，但是写不出代码，很是尴尬，所以今天就花点时间把知识回顾⼀下，并把代码实现。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1：模式匹配模式匹配(Pattern Matching) 即⼦串定位运算（Index函数）。
算法⽬的：确定主串中所含⼦串第⼀次出现的位置（定位） ——即如何实现 Index(S,T,pos)函；初始条件：串S和T存在，T是⾮空串，1≤pos≤StrLength(s) 操作结果：若主串S中存在和串T值相同的⼦串，则返回它在主串S中第pos个字符之后第⼀次出现的位置；否则函数值为0。
注：S称为被匹配的串，T称为模式串。
若S包含串T，则称“匹配成功”。
否则称 “匹配不成功” 。
常见的两种算法：BF算法（⼜称古典或经典的、朴素的、穷举的）KMP算法（特点：速度快）2：BF算法① BF算法设计思想：将主串的第pos个字符和模式的第1个字符⽐较，若相等，继续逐个⽐较后续字符；若不等，从主串的下⼀字符（pos+1）起，重新与第⼀个字符⽐较。
直到主串的⼀个连续⼦串字符序列与模式相等。
返回值为S中与T匹配的⼦序列第⼀个字符的序号，即匹配成功。
否则，匹配失败，返回值 0 .BF算法的伪代码：算法C++实现1 #include<bits/stdc++.h>23using namespace std;4int BF(string a,int stra,string b,int strb)5 {6int i=0;7int j=0;8while(i<stra && j<strb) 9 {10if(a[i]==b[j])11 {12 i++;13 j++;14 }15else16 {17 i=i-j+1;18 j=0;19 }20 }21if(j>=strb){22 cout << "匹配成功"; 23return i-strb;24 } else25 {26 cout << "匹配失败"; 27return0;28 }29 }30int main()31 {32string a,b;33 cin >> a >> b;34int stra=a.length(); 35int strb=b.length(); 36 BF(a,stra,b,strb);37return0;38 }3：KMP算法算法C++实现1 #include<bits/stdc++.h>23using namespace std;4int next[1000];5void get_next(string str,int stra)6 {7int i=1;8 next[1]=0;9int j=0;10while(i<stra)11 {12if(j==0 || str[i]==str[j])13 {14 ++i;15 ++j;16 next[i]=j;17 }else18 {19 j=next[j];20 }21 }22 }2324int KMP(string a,int stra,string b,int strb) 25 {26int j=1;27int i=0;28while(i<stra && j<=strb)29 {30if(j==0 || a[i]==b[j-1] ){31 i++;32 j++;33 }34else35 {36 j=next[j];37 }38 }39if(j>strb) {40 cout << "匹配成功" << endl;41return i-strb;42 }else43 {44 cout << "匹配失败" << endl;45return -1;46 }47 }48int main()49 {50 memset(next,0,sizeof(next));51string a,b;52 cin >> a >> b;53int stra=a.length();54int strb=b.length();55 get_next(b,strb);56int m=KMP(a,stra,b,strb);57if(m!=-1)58 {59 cout << "匹配的位置在" << m << endl;60 }61return0;62 }。
实验三串的模式匹配⼀、实验⽬的1、了解串的基本概念2、掌握串的模式匹配算法的实现⼆、实验预习说明以下概念1、模式匹配：数据结构中字符串的⼀种基本运算，给定⼀个⼦串，要求在某个字符串中找出与该⼦串相同的所有⼦串。
2、BF算法：BF算法，即暴⼒(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将⽬标串S的第⼀个字符与模式串T的第⼀个字符进⾏匹配，若相等，则继续⽐较S的第⼆个字符和 T的第⼆个字符；若不相等，则⽐较S的第⼆个字符和T的第⼀个字符，依次⽐较下去，直到得出最后的匹配结果。
BF算法是⼀种蛮⼒算法。
3、KMP算法：KMP算法是⼀种改进的字符串匹配算法，KMP算法的核⼼是利⽤匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的⽬的。
具体实现就是通过⼀个next()函数实现，函数本⾝包含了模式串的局部匹配信息。
三、实验内容和要求1、阅读并运⾏下⾯程序，根据输⼊写出运⾏结果。
#include<stdio.h>#include<string.h>#define MAXSIZE 100typedef struct{char data[MAXSIZE];int length;}SqString;int strCompare(SqString *s1,SqString *s2); /*串的⽐较*/void show_strCompare();void strSub(SqString *s,int start,int sublen,SqString *sub);/*求⼦串*/void show_subString();int strCompare(SqString *s1,SqString *s2){int i;for(i=0;i<s1->length&&i<s2->length;i++)if(s1->data[i]!=s2->data[i])return s1->data[i]-s2->data[i];return s1->length-s2->length;}void show_strCompare(){SqString s1,s2;int k;printf("\n***show Compare***\n");printf("input string s1:");gets(s1.data);s1.length=strlen(s1.data);printf("input string s2:");gets(s2.data);s2.length=strlen(s2.data);if((k=strCompare(&s1,&s2))==0)printf("s1=s2\n");else if(k<0)printf("s1<s2\n");elseprintf("s1>s2\n");printf("\n***show over***\n");}void strSub(SqString *s,int start,int sublen,SqString *sub){int i;if(start<1||start>s->length||sublen>s->length-start+1){sub->length=0;}for(i=0;i<sublen;i++)sub->data[i]=s->data[start+i-1];sub->length=sublen;}void show_subString(){SqString s,sub;int start,sublen,i;printf("\n***show subString***\n");printf("input string s:");gets(s.data);s.length=strlen(s.data);printf("input start:");scanf("%d",&start);printf("input sublen:");scanf("%d",&sublen);strSub(&s,start,sublen,&sub);if(sub.length==0)printf("ERROR!\n");else{printf("subString is :");for(i=0;i<sublen;i++)printf("%c",sub.data[i]);}printf("\n***show over***\n");}int main(){int n;do {printf("\n---String---\n");printf("1. strCompare\n");printf("2. subString\n");printf("0. EXIT\n");printf("\ninput choice:");scanf("%d",&n);getchar();switch(n){case 1:show_strCompare();break;case 2:show_subString();break;default:n=0;break;}}while(n);return 0;}运⾏程序输⼊：1studentstudents2Computer Data Stuctures104运⾏结果：2、实现串的模式匹配算法。
Brute Force(BF或蛮力搜索) 算法：这是世界上最简单的算法了。
首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。
速度最慢。
那么，怎么改进呢？我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？当然是可以的。
我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。
^_^注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。
KMP算法首先介绍的就是KMP 算法。
这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。
也难怪，呵呵。
谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible <The Art of Computer Programming>( 业内人士一般简称TAOCP). 稍稍提一下，有个叫H.A.Simon 的家伙，不仅拿了Turing Award ，顺手拿了个Nobel Economics Award ，做了AI 的爸爸，还是Chicago Univ 的Politics PhD ，可谓全才。
KMP 的思想是这样的：利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离比如模式串ababac 这个时候我们发现在c 处不匹配，然后我们看c 前面那串字符串的最大相等前后缀，然后再来移动下面的两个都是模式串，没有写出来匹配串原始位置ababa c移动之后aba bac因为后缀是已经匹配了的，而前缀和后缀是相等的，所以直接把前缀移动到原来后缀处，再从原来的c 处，也就是现在的第二个b 处进行比较。
BF算法KMP算法BM算法BF算法（Brute-Force算法）是一种简单直接的字符串匹配算法。
它的基本思想是从主串的第一个字符开始，逐个与模式串的字符进行比较，如果匹配失败，则主串的指针向右移动一位，继续从下一个字符开始匹配。
重复这个过程，直到找到匹配的子串或者主串遍历完毕。
BF算法的时间复杂度是O(n*m)，其中n和m分别是主串和模式串的长度。
当模式串较长时，算法的效率较低。
但是BF算法的实现简单，易于理解，对于较短的模式串和主串，仍然是一种可行的匹配算法。
KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，它利用了模式串内部的信息，避免了不必要的比较。
KMP算法引入了一个next数组，用于记录模式串中每个位置对应的最长可匹配前缀子串的长度。
KMP算法的基本思想是，当匹配失败时，不是简单地将主串指针右移一位，而是利用next数组将模式串的指针向右移动若干位，使得主串和模式串中已经匹配的部分保持一致，减少比较次数。
通过预处理模式串，计算出next数组，可以在O(n+m)的时间复杂度内完成匹配。
BM算法（Boyer-Moore算法）是一种高效的字符串匹配算法，它结合了坏字符规则和好后缀规则。
BM算法从模式串的末尾开始匹配，根据坏字符规则，如果在匹配过程中发现了不匹配的字符，可以直接将模式串向右滑动到该字符在模式串中最右出现的位置。
BM算法还利用了好后缀规则，当发现坏字符后，可以根据好后缀的位置和模式串的后缀子串进行匹配，从而减少不必要的比较。
通过预处理模式串，计算出坏字符规则和好后缀规则对应的滑动距离，可以在最坏情况下实现O(n/m)的时间复杂度。
总结来说，BF算法是一种简单直接的字符串匹配算法，适用于较短的模式串和主串；KMP算法通过预处理模式串，利用next数组减少比较次数，提高了匹配效率；BM算法结合了坏字符规则和好后缀规则，利用了更多的信息，是一种高效的字符串匹配算法。
Boyer-Moore算法Boyer-Moore算法（简称BM算法）是一种高效的字符串匹配算法，由Robert S. Boyer和J Strother Moore于1977年提出。
相比于其他字符串匹配算法，如Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。
1. 算法原理BM算法的核心思想是从待匹配的字符串的末尾进行比较，而不是从开头。
具体来说，算法首先获取模式串（待搜索的子串）的最后一个字符，然后在待匹配的字符串中以模式串的长度为步长，从后往前进行比较。
如果比较的过程中发现存在不匹配的字符，算法会根据预处理的规则跳过一定范围的字符，从而实现快速的搜索。
而将模式串与待匹配的字符串进行比较的过程中，算法会根据预处理的规则将模式串向后移动一定的位置，以加快搜索的速度。
2. 算法流程BM算法的主要流程可以概括为以下几个步骤：1.预处理模式串：–建立一个坏字符规则表，记录每个字符在模式串中最右出现的位置。
–建立好后缀规则表，记录每个后缀子串在模式串中的出现位置。
2.匹配过程：–从待匹配字符串的末尾与模式串的末尾开始比较。
–如果遇到坏字符（即不匹配的字符），根据坏字符规则表和好后缀规则表进行移动。
–当模式串完全匹配，则表示找到了一个匹配的字符串。
3. 算法优势BM算法在字符串匹配问题中具有较高的效率，其优势主要体现在以下几个方面：•坏字符规则表：BM算法通过预处理模式串，建立坏字符规则表，从而实现在找到不匹配的字符时能够快速将模式串右移，从而跳过一定范围的字符。
这种方式可以大幅减少比较的次数，提高搜索效率。
•好后缀规则表：BM算法还通过预处理模式串，建立好后缀规则表。
当发现不匹配的字符时，算法会根据好后缀规则表的信息将模式串向后移动一定位置，以加快搜索速度。
•时间复杂度低：相比于Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。
数据结构之串的匹配串的匹配应⽤⼗分⼴泛，⽐如搜索引擎、拼写检查、语⾔翻译、数据压缩等等，都需要进⾏串的匹配。
串的模式匹配设有两个字符串 S 和 T ，设 S 为主串（正⽂串），T 为⼦串（模式），在主串 S 中查找与模式 T 相匹配的⼦串，如果匹配成功，确定相匹配的⼦串中第⼀个字符在主串 S 中出现位置。
下⾯介绍两种算法：BF 算法和 KMP 算法。
⼀、BF算法1、分别利⽤计数指针 i 和 j 指⽰主串 S 和模式 T 中当前待⽐较的字符位置。
2、如果⽐较未到结尾，则循环执⾏以下操作：① S.ch[ i ] 和 T.ch[ j ] ⽐较，若相等，则 i++; j++; 继续⽐较后续字符。
②若不等，指针后退重新匹配，从主串的下⼀个字符(i = i - j + 2)起再重新和模式的第⼀个字符(j = 1)⽐较。
3、如果 j > T.length，说明匹配成功，返回和模式 T 第⼀个字符相等的字符在主串中的序号(i - T.length)，否则失败，返回0。
该算法的时间复杂度为 O(m × n)代码如下：1 #include<stdio.h>2 #include<stdlib.h>3 #include<string.h>4#define MAXSIZE 205 typedef struct6 { // 定义数组存储字符串7char ch[MAXSIZE+1];8int length;9}String;10int index_BF(String S, String T);11int main()12{13int flag;14 String S, T;15 printf("请输⼊主串S:");16 gets(S.ch + 1);17 S.length = strlen(S.ch+1);18 S.ch[0] = (char)S.length;19 printf("请输⼊模式串T:");20 gets(T.ch + 1);21 T.length = strlen(T.ch+1);22 T.ch[0] = (char)T.length;23 flag = index_BF(S, T);24if (flag)25 printf("匹配成功，在第%d位。
数据结构面试之十四——字符串的模式匹配题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
十四、字符串的模式匹配1. 模式匹配定义——子串的定位操作称为串的模式匹配。
2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法）【算法思想】：第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。
第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。
比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。
对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。
【算法实现】：//普通字符串匹配算法的实现int Index(char* strS, char* strT, int pos){//返回strT在strS中第pos个字符后出现的位置。
int i = pos;int j = 0;int k = 0;int lens = strlen(strS);int lent = strlen(strT);while(i < lens && j < lent){if(strS[i+k] == strT[j]){++j; //模式串跳步++k; //主串(内)跳步}else{i = i+1;j=0; //指针回溯，下一个首位字符k=0;}}//end iif(j >= lent){return i;}else{return 0;}}//end[算法时间复杂度]：设主串长度为m,模式串的长度为n。
一般情况下n<m。
24、蛤蟆的数据结构笔记之二十四串的模式匹配算法 本篇名言：“燧石受到的敲打越厉害，发出的光就越灿烂。 -- 马克思”
来看下两个算法，BF和KMP算法在串的模式匹配中实现。
1. BF算法
BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。 首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。 该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。
如下图1 ： 2. KMP算法 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
主串：a b a c a a b a c a b a c a b a a b b，下文中我们称作T 模式串：a b a c a b，下文中我们称作W 在暴力字符串匹配过程中，我们会从T[0] 跟 W[0] 匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。 然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。 比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。 在第一次匹配过程中 T: a b a c a a b a c a b a c a b a a b b M: a b a c ab 在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠： T: a b a c aab a c a b a c a b a a b b M: a b a c ab 然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
数据结构- 串的模式匹配算法：BF和KMP算法Brute-Force算法的思想Brute-Force算法的基本思想是：1) 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。
2) 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
Brute-Force算法的实现c语言实现：1.// Test.cpp : Defines the entry point for the console application.2.//3.#include "stdafx.h"4.#include <stdio.h>5.#include "stdlib.h"6.#include <iostream>ing namespace std;8.9.//宏定义10.#define TRUE 111.#define FALSE 012.#define OK 113.#define ERROR 014.15.#define MAXSTRLEN 10016.17.typedef char SString[MAXSTRLEN + 1];18./************************************************************************/19./*20.返回子串T在主串S中第pos位置之后的位置，若不存在，返回021.*/22./************************************************************************/23.int BFindex(SString S, SString T, int pos)24.{25.if (pos <1 || pos > S[0] ) exit(ERROR);26.int i = pos, j =1;27.while (i<= S[0] && j <= T[0])28. {29.if (S[i] == T[j])30. {31. ++i; ++j;32. } else {33. i = i- j+ 2;34. j = 1;35. }36. }37.if(j > T[0]) return i - T[0];38.return ERROR;39.}40.41.42.43.void main(){44. SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};45. SString T = {5,'a','b','c','a','c'};46.int pos;47. pos = BFindex( S, T, 1);48. cout<<"Pos:"<<pos;49.}2.1 算法思想：每当一趟匹配过程中出现字符比较不等时，不需要回溯I指针，而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。
字符串模式匹配---BF算法字符串模式匹配有着广泛的应用，如求最大公共子串、最长回文字符串、L-Gap、数据压缩、DNA序列匹配等问题。
所谓模式匹配就是在目标字符串中寻找字串的过程，要寻找的字串即为模式。
BF(Bruce Force)算法可以说是模式匹配算法中最简单、最容易理解的一个。
原理很简单。
其基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的字串，则匹配失败。
该算法较为简单，代码如下：//start 为从第start位置的字符开始比较，默认为0int BF(char s[], char d[], int start = 0){char *p = s + start; //记录开始比较的位置int index = start - 1; //记录位置，以便成功时返回字串在主串的位置char *q = d;char *tmp;while (*p != '\0'){tmp = p;++index;while (*q != '\0' && *tmp != '\0' && *tmp == *q){++tmp;++q;}if (*q == '\0') //匹配成功，返回结果return index;else //主串和模式串回溯{++p;q = d;}}return -1; //匹配失败}设有主串s和子串t，子串t定位是指在主串s中找到一个与子串t相等的子串。
通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。
模式匹配成功是指在目标串s中找到一个模式串t。
传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。
这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。
KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。
KMP算法是字符串模式匹配中的经典算法。
和BF 算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。
下面说说KMP算法的原理。
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。
简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。
可以证明它的时间复杂度为O(m+n).。
一．简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S [ ], char T [ ], int pos ){/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符起存在和串 T 相同的子串，则称匹配成功，返回第一个这样的子串在串 S 中的下标，否则返回 -1 */int i = pos, j = 0;while ( S[i+j] != '/0'&& T[j] != '/0')if ( S[i+j] == T[j] )j ++; // 继续比较后一字符else{i ++; j = 0; // 重新开始新的一轮匹配}if ( T[j] == '/0')return i; // 匹配成功返回下标elsereturn -1; // 串S中(第pos个字符起)不存在和串T相同的子串} // Index_BF此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。
即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。
例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。
如图：当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。
如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。
如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。
如图：又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。
这次T中的所有字符都和S中相应的字符匹配了。
函数返回T在S中的起始下标3。
如图：二. KMP匹配算法还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值（next[5]=2，为什么？后面讲），直接比较S[5] 和T[2]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。
最终在S中找到了T。
如图：KMP匹配算法和简单匹配算法效率比较，一个极端的例子是：在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”,简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。
如果使用KMP匹配算法，就不必回溯.对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O (m+n)，因此在多数的实际应用场合下被应用。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。
看前面的例子。
为什么T[5]==’d’的模式函数值等于2（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同，且T[5]==’d’不等于开始的两个字符之后的第三个字符（T[2]=’c’）.如图：也就是说，如果开始的两个字符之后的第三个字符也为’d’,那么，尽管T[5]==’d’的前面有2个字符和开始的两个字符相同，T[5]==’d’的模式函数值也不为2，而是为0。
前面我说：在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值，直接比较S[5] 和T[2]是否相等。
为什么可以这样？刚才我又说：“（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同”。
请看图：因为，S[4] ==T[4]，S[3] ==T[3]，根据next[5]=2，有T[3]==T[0]，T[4] ==T[1]，所以S[3]==T[0]，S[4] ==T[1]（两对相当于间接比较过了），因此，接下来比较S[5] 和T[2]是否相等。
有人可能会问：S[3]和T[0]，S[4] 和T[1]是根据next[5]=2间接比较相等，那S[1]和T[0]，S[2] 和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，而T[0] != T[1], T[1] != T[2],==> S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。
那么，怎么求串的模式函数值next[n]呢？（本文中next 值、模式函数值、模式值是一个意思。
）三. 怎么求串的模式值next[n]定义：（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad”则 next[6]=-1，因T[3]=T[6]（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。
T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1]且T[j] != T[k].（1≤k<j）;(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
举例：01）求T=“abcac”的模式函数的值。
next[0]= -1 根据（1）next[1]=0 根据 (4) 因（3）有1<=k<j;不能说，j=1,T[j-1]==T[0]next[2]=0 根据 (4) 因（3）有1<=k<j;（T[0]=a）!=（T[1]=b）next[3]= -1 根据 (2)next[4]=1 根据 (3) T[0]=T[3] 且 T[1]=T[4]即若T=“abcab”将是这样：为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据(3)”且T[j] != T[k]”被划入（4）。
02）来个复杂点的，求T=”ababcaabc”的模式函数的值。
