当前位置：文档之家 › 第4章串第2讲-串的模式匹配

第4章串第2讲-串的模式匹配

  • 格式：pptx
  • 大小：146.27 KB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

数据结构串串的基本概念串的存储结构与实现串的模式匹配

数据结构串串的基本概念串的存储结构与实现串的模式匹配
t.ch[i]=s1.ch[i]; for(i=s1.length;i<t.length;i++)
t.ch[i]=s2.ch[i-s1.length]; }
串删除
void strdelete(Hstring &s,int pos,int len) {
if(pos<1||pos>s.length-len+1||len<0||len>s.length){ cout<<"删除位置不合法"<<endl; return;
int flag=0; int i=0,j=1; if(s1[0]+s2[0]<=MAXSTRLEN) {
for(i=1;i<=s1[0];i++) t[i]=s1[i];
for(i=s1[0]+1;i<=s1[0]+s2[0];i++) t[i]=s2[j++];
t[0]=s1[0]+s2[0]; flag=1; //未截断 }
strempty(s) 初始条件：s为一个串 操作结果：若s为空串，则返回1
strcopy(&t,s) 初始条件：s为一个串 操作结果：把串s复制给t
strncpy(&sub,s,pos,len) 初始条件：s为一个串，pos为起始位置， 1≤pos≤strlength(s)-1,len≥0 操作结果：用sub返回串s的第pos个字符开⑩长度为len的子串
例：模式串t=“abcac”和主串s=“ababcabcaccabbc”匹配过程
第三二一 趟 a b a b c a b c a c c a b b c i=112734568901

串的模式匹配算法

串的模式匹配算法

串串（String）又叫做字符串，是一种特殊的线性表的结构，表中每一个元素仅由一个字符组成。

随着计算机的发展，串在文字编辑、词法扫描、符号处理以及定理证明等诸多领域已经得到了越来越广泛的应用。

第一节串的定义和表示1、串的逻辑结构定义串是由零个到任意多个字符组成的一个字符序列。

一般记为：S=’ a1a2a3……a n’(n>=0)其中S为串名，序列a1a2a3……a n为串值，n称为串的长度，我们将n=0的串称为空串(null string)。

串中任意一段连续的字符组成的子序列我们称之为该串的子串，字符在序列中的序号称为该字符在串中的位置。

在描述中，为了区分空串和空格串(s=‘’)，我们一般采用来表示空串。

2、串的基本操作串一般包含以下几种基本的常用操作：1、length(S)，求S串的长度。

2、delete(S,I,L)，将S串从第I位开始删除L位。

3、insert(S,I,T)，在S的第I位之前插入串T。

4、str(N,S)，将数字N转化为串S。

5、val(S,N,K)，将串S转化为数字N；K的作用是当S中含有不为数字的字符时，K记录下其位置，并且S没有被转化为N。

3、串的储存结构一般我们采用以下两种方式保存一个串：1、字符串类型，描述为：const n=串的最大长度type strtype=string[n]这里由于tp的限制，n只能为[1..255]。

在fp或者delphi中，我们还可以使用另外一种类型，描述为：const n=串的最大长度type strtype=qstring[n]这里的n就没有限制了，只要空间允许，开多大都可以。

2、数组来保存，描述为：const n=串的最大长度type strtype=records:array[1..n] of char;len:0..n;end;第二节模式匹配问题与一般的线性表不同，我们一般将串看成一个整体，它有一种特殊的操作——模式匹配。

《数据结构与算法(C++语言版)》第4章_串

《数据结构与算法(C++语言版)》第4章_串

串函数与串的类定义
• 常用的 常用的C++串函数 串函数 • C++的串库（string.h）中提供了许多字符串的操作函数，几 个常用的C++字符串函数及其使用方法如下。 •假设已有以下定义语句：
串函数与串的类定义
• （1）串拷贝函数 • char *strcpy(char *s1, const char *s2)，将字符串s2复制到字 符串数组s1中，返回s1的值。 • char *strncpy(char *s1, const char *s2, size_tn)将字符串s2中最 多n个字符复制到字符串数组s1中，返回s1的值。 • 例如：
串函数与串的类定义
• （3）串比较函数 • int strcmp(const char *s1, const char *s2)，比较字符串s1和字 符串s2。函数在s1等于、小于或大于s2时，分别返回0、小 于0或者大于0的值。 • int strncmp(const char *s1, const char *s2, size_tn)比较字符串 s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2 时，分别返回0、小于0或者大于0的值。 • 例如：
串模式匹配
• 无回溯的匹配算法 • 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。

串的模式匹配算法实验报告

串的模式匹配算法实验报告

竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告篇一：串的模式匹配算法串的匹配算法——bruteForce(bF)算法匹配模式的定义设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。

通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。

模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。

bF算法brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。

以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。

实现代码如下：/*返回子串T在主串s中第pos个字符之后的位置。

若不存在，则函数返回值为0./*T非空。

intindex(strings,stringT,intpos){inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1；}if(j>T[0])returni-T[0];elsereturn0;}}bF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。

最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).篇二：数据结构实验报告-串实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：bF和Kmp。

3、了解串的应用。

【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。

数据结构-第4章 串

数据结构-第4章 串
真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

串的模式匹配算法

串的模式匹配算法字符串模式匹配是计算机科学中一种常用的算法。

它是一种检索字符串中特定模式的技术，可以用来在字符串中查找相应的模式，进而完成相应的任务。

字符串模式匹配的基本思想是，用一个模式串pattern去匹配另一个主串text，如果在text中找到和pattern完全匹配的子串，则该子串就是pattern的匹配串。

字符串模式匹配的过程就是在text中搜索所有可能的子串，然后比较它们是否和pattern完全匹配。

字符串模式匹配的算法有很多，其中著名的有暴力匹配算法、KMP算法、BM算法和Sunday算法等。

暴力匹配算法是最简单也是最常用的字符串模式匹配算法，其思想是从主串的某一位置开始，依次比较pattern中每一个字符，如果某个字符不匹配，则从主串的下一位置重新开始匹配。

KMP算法（Knuth-Morris-Pratt算法）是一种更为高效的字符串模式匹配算法，它的特点是利用了已匹配过的字符的信息，使搜索更加有效。

它的实现思想是，在pattern中先建立一个next数组，next数组的值代表pattern中每个字符前面的字符串的最大公共前缀和最大公共后缀的长度，这样可以在主串和模式串匹配失败时，利用next数组跳转到更有可能匹配成功的位置继续搜索，从而提高字符串模式匹配的效率。

BM算法（Boyer-Moore算法）也是一种高效的字符串模式匹配算法，它的实现思想是利用主串中每个字符最后出现的位置信息，以及模式串中每个字符最右出现的位置信息来跳转搜索，从而减少不必要的比较次数，提高搜索效率。

Sunday算法是一种简单而高效的字符串模式匹配算法，它的实现思想是，在主串中搜索时，每次从pattern的最右边开始比较，如果不匹配，则根据主串中下一个字符在pattern中出现的位置，将pattern整体向右移动相应位数，继续比较，这样可以减少不必要的比较次数，提高算法的效率。

字符串模式匹配算法的应用非常广泛，它可以用来查找文本中的关键字，检查一个字符串是否以另一个字符串开头或结尾，查找文本中的模式，查找拼写错误，检查字符串中是否包含特定的字符等。

串

初始条件：串S和T存在。 操作结果:若S>T，则返回值>0；若S = T，则返回值=0；若S<T，则返回值<0.
ClearString (&S)
初始条件：串S存在。 操作结果：将S清为空串。
Concat (&T , S1, S2)
初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。
Status ClearString(HString &S) { //将S清为空串. if(S.ch) { free(S.ch); S.ch=NULL;} S.length=0; return OK; }// ClearString
Status Concat(HString &T, HString S1, HString S2)
int Strlength(HString S) { return S.length; }
int StrCompare(HString S, HString T) { //若S>T，则返回值>0；若S = T，则返回值=0；若S<T，则返回值<0 for( i=0; i< S.length && i< T.length; ++i ) if(S.ch[i]!= T.ch[i]) return S.ch[i]-T.ch[i]; return S.length- T.length; }
• 二、串的抽象数据类型的定义
ADT String { 数据对象：D={ai| ai∈CharacterSet； i=1,2,…,n,；n≥0} 数据关系：R1={<ai-1, ai>| ai-1, ai∈D； i= 2,…,n} 基本操作： StrAssign (&T , chars)

简述串的模式匹配原理

简述串的模式匹配原理嘿，咱聊聊串的模式匹配原理呗！这串的模式匹配，听着挺神秘，其实也不难理解。

就像在一堆宝藏里找宝贝。

啥是串的模式匹配呢？简单说，就是在一个大字符串里找一个小字符串。

这就像在一片大海里找一条小鱼。

你得有办法才能找到它。

比如说，你想在一篇文章里找一个特定的词，这就是串的模式匹配。

那怎么找呢？有好几种方法呢。

一种是暴力匹配。

这就像一个愣头青，一个一个地比对。

从大字符串的开头开始，一个字符一个字符地和小字符串比对。

如果不一样，就往后移一个字符，继续比对。

这就像在一堆沙子里找一颗小石子，得一颗一颗地找。

虽然有点笨，但是有时候也能管用。

还有一种是KMP 算法。

这就像一个聪明的侦探，有自己的一套方法。

它会先分析小字符串的特点，然后根据这些特点来快速匹配。

比如说，如果在比对的过程中发现不一样了，它不会像暴力匹配那样从头开始，而是根据之前的分析，直接跳到合适的位置继续比对。

这就像你知道了宝藏的线索，就能更快地找到宝藏。

串的模式匹配有啥用呢？用处可大了。

比如说，在文本编辑软件里，你想查找一个特定的词或者句子，就用到了串的模式匹配。

还有在搜索引擎里，也是用串的模式匹配来找到你想要的信息。

这就像你有一把神奇的钥匙，能打开知识的大门。

你说要是没有串的模式匹配，那会咋样呢？那找东西可就麻烦了。

就像在一个乱七八糟的房间里找东西，没有头绪，得翻个底朝天。

有了串的模式匹配，就像有了一个指南针，能让你更快地找到你想要的东西。

总之，串的模式匹配就像一个神奇的工具，能在大字符串里找到小字符串。

咱可得好好理解它，让它为我们的生活带来更多的便利。

数据结构—串的模式匹配

数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。

本文档将详细介绍串的模式匹配算法及其实现。

2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。

具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。

2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。

3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。

3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。

具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。

4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。

具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。

5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。

具体步骤如下：1.计算模式串的哈希值。

2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

a
2
b
3
前面的匹配过程：
i=3 j=3 i=3 j=2 将s[i]与 t[2]匹配 i=3 j=1 将s[i]与 t[1]匹配 i=3 j=0 i=3 j=-1 将s[i+1]与 t[0]匹配
将s[i]与 t[3]匹配
将s[i]与 t[0]匹配
因为t[3]=t[2]=t[1]=t[0]='a'
是不必要的
0 1 2 3 4
失败： i=3 j=1，j=next[1]=0
21/29
j t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
a
2
b
3
0 1 2 3 4 5 6 7 8
i=3 j=0
s: t:
a a a b a a a a b a a a a b
0 1 2 3 4
失败： i=3 j=0，j=next[0]=-1
目标串s
是子串吗？
模式匹配
模式串t
成功是指在目标串s中找到一个模式串t t是s的子串，返回t 在s中的位置。 不成功则指目标串s中不存在模式串t t不是s的子串，返回-1。
1/29
4.4.1 Brute-Force算法
Brute-Force简称为BF算法，亦称简单匹配算法。采用穷 举的思路。 s: t: a a a a b c d
i=3 j=2
s: t:
a a a b a a a a b a a a a b
0 1 2 3 4
失败： i=3 j=2，j=next[2]=1
20/29
j t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
a
2
b
3
0 1 2 3 4 5 6 7 8
i=3 j=1
s: t:
a a a b a a a a b a a a a b
∴ nextval[1]=nextval[0]=-1
nextval[0]=-1 当t[j]=t[next[j]]时： nextval[j]=nextval[next[j]] 否则： nextval[j]=next[j]
用nextval取代next，得到改进的KMP算法。
25/29
使用改进后的KMP算法示例：
=
“ tj-ktj-k+1…tj-1 ”
t[j]前面的k个字符
例如，t= “a b a b c” 考虑t[4]='c' 有t0t1＝ t2t3 = "ab" k=2 所以next[4] = k = 2。
0 1 2 3 4
10/29
归纳起来，定义next[j]数组如下:
开头的k个字符 后面的k个字符
a a a b b a c c b c b c 匹配成功
算法的思路是从s的每一个字符开始依次与t的字符进行匹配。
2/29
例如，设目标串s=“aaaaab”，模式串t=“aaab”。s的长度为n （n=6），t的长度为m（m=4）。BF算法的匹配过程如下。
i
s： t：
a a
j
a a
a a
MAX{ k | 0<k<j，且“t0t1…tk-1” = “tj-ktj-k+1…tj-1”}
next[j]=
当此集合非空时 -1 0 当j=0时 其他情况
t=“aaab”对应的next数组如下:
j t[j] next[j] 0 a -1 1 a 0 2 a 1 3 b 2
t0=t1="a"t0t1=t1t2="aa" 11/29
a b
a
b
匹配失败： i=i-j+1=1 （回退） j=0 （从头开始）
3/29
i=1，j=0
i
s： t：
a a
j
a a
a a
a b
a
b
匹配失败： i=i-j+1=2（回退） j=0（从头开始）
4/29
i=2，j=0
i
s： t：
a a
j
a a
a a
a b
a
b
匹配成功： i=6，j=4 返回i-t.length=2
KMP算法
28/29
━━本讲完━━
29/29
说明：本题为2015年全国考研题
j t[j] 0 1 2 3 4 5
a
-1
b
0
a
0
a
1
b
1
c
next[j]
2
选C
16/29
17/29
设目标串s=“aaabaaaab”，模式串t=“aaaab”。KMP模
式匹配过程。
求t的next：
j
t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
a
2
b
3
18/29
next[j]的含义 （1）next[j]=k表示什么信息？
说明模式串t[j]之前有k个字符已成功匹配，下一趟应从t[k]开始 匹配。
0 1 2 3
s: t:
a a a a
a b
b
a
a a
a a
b b
next[2]=1
（2）next[j]=-1表示什么信息？
说明模式串t[j]之前没有任何用于加速匹配的信息，下一趟应从 t的开头即j++ j=0开始匹配。 如t=“abcd”，next[0]=next[1]=next[2]=next[3]=-1。
15/29
【例（补充）】 已知字符串S为
“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP 算法进行匹配，第一次出现“失配”(s[i] != t[j])时，i=j=5，则 下次开始匹配时，i和j的值分别是 。 A.i=1，j=0 B.i=5，j=0 C.i=5，j=2 D.i=6，j=2
22/29
j t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
a
2
b
3
0 1 2 3 4 5 6 7 8
因为j=-1： i++; j++;
s: t:
a a a b a a a a b a a a a b
0 1 2 3 4
成功： 返回4
23/29
j t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
该算法较BF算法有较大改进，主要是消除了主串指针
的回溯，从而使算法效率有了某种程度的提高。
8/29
KMP算法用nab”。
开始匹配的字符 下次开始匹配的字符
0 1 2 3 4 5 s: a a a a a b
t: a a a b
12/29
由模式串t求next值的算法：
13/29
KMP算法：
14/29
KMP算法分析 设串s的长度为n，串t长度为m。
在 KMP 算法中求 next 数组的时间复杂度为 O(m) ，在后
面的匹配中因主串s的下标不减即不回溯，比较次数可记为n， 所以KMP算法平均时间复杂度为O(n+m)。 最坏的时间复杂度为O(n × m)。
5/29
对应的BF算法如下：
int index(SqString s,SqString t) { int i=0, j=0; while (i<s.length && j<t.length) { if (s.data[i]==t.data[j]) //继续匹配下一个字符 { i++; //主串和子串依次匹配下一个字符 j++; } else //主串、子串指针回溯重新开始下一次匹配 { i=i-j+1; //主串从下一个位置开始匹配 j=0; //子串从头开始匹配 } } if (j>=t.length) return(i-t.length); //返回匹配的第一个字符的下标 else return(-1); //模式匹配不成功 }
从t中发现：b前面有2个字符和开头的2个字符相同
用一个数组next保存：next[3]=2
下次匹配的字符：s[3]和t[next[3]]即t[2]
9/29
next[j]是指t[j]字符前有多少个字符与t开头的字符相同。 模式串t存在某个k（0＜k＜j），使得以下成立:
“t0t1…tk -1”
开头的k个字符
6/29
BF算法分析：
算法在字符比较不相等，需要回溯（即i=i-j+1）：即退 到s中的下一个字符开始进行继续匹配。 最好情况下的时间复杂度为O(m)。
最坏情况下的时间复杂度为O(n×m)。
平均的时间复杂度为O(n×m)。
7/29
4.3.2 KMP算法
KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同 提出的，简称KMP算法。
j t[j] next[j]
0
1
2
3
4
a
-1
a
0
a
1
a
2
b
3
0 1 2 3 4 5 6 7 8
s: t:
a a a b a a a a b a a a a b
0 1 2 3 4
失败： i=3 j=3，j=next[3]=2