第4章-算法数据结构ppt课件.ppt

第第4 4章章 串串字符串一般简称串字符串一般简称串【学习目标】【学习目标】1.1.理解理解“串串”类型定义中各基本操作的特点，并能正确类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。利用它们进行串的其它操作。2.2.理解串类型的各种存储表示方法。理解串类型的各种存储表示方法。3.3.理解串匹配的各种算法。理解串匹配的各种算法。【重点和难点】【重点和难点】相对于其它各个知识点而言，本章非整个课程的重点，相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的作。本章的难点是理解实现串匹配的KMP算法的思想，但算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。它不属本章学习的基本要求，更不是重点学习内容。为何要单独讨论为何要单独讨论“串串”类型？类型？1 1）程序设计中，处理对象很多都是串类型。程序设计中，处理对象很多都是串类型。2 2）字符串操作比其他数据类型更复杂（如拷贝、字符串操作比其他数据类型更复杂（如拷贝、连接操作）。连接操作）。4.1 4.1 串类型的定义串类型的定义 4.2 4.2 串的表示和实现串的表示和实现 4.3 4.3 串的模式匹配算法串的模式匹配算法4.1 4.1 串类型的定义串类型的定义4.1 4.1 串类型定义串类型定义 串串(string)string):即字符串，是由零个或多个字符即字符串，是由零个或多个字符组成的组成的有限序列有限序列。是是数据元素为单个字符数据元素为单个字符的特殊线性表。的特殊线性表。记为：记为：s =a1 a2.an (n0)串名串名串值（用串值（用 括起来）括起来）ai(0i n)可以是字母、数字或其它字符；可以是字母、数字或其它字符；4.1 4.1 串类型定义串类型定义长度：长度：串中字符数目串中字符数目 n n 称为串的称为串的长度长度。空串：空串：长度为长度为 0 的字符称为的字符称为空串空串(Null string)，我们用我们用表示表示“空串空串”。空格串：空格串：由一个或多个空格组成的串由一个或多个空格组成的串 称为称为空格串空格串(black string)。问：空串和空格串有无区别？问：空串和空格串有无区别？答：答：有区别有区别。空串空串(Null String)是指长度为零的串；是指长度为零的串；而空格串而空格串(Blank String),),是指包含一个或多个空格字是指包含一个或多个空格字符符 (空格键空格键)的字符串。它的长度为空格字符的个数的字符串。它的长度为空格字符的个数空串是任意串的子串；任意串空串是任意串的子串；任意串S S都是自身的子串，都是自身的子串，除除S S本身外，本身外，S S的其它子串称为的其它子串称为“真子串真子串”4.1 4.1 串类型定义串类型定义子串子串：串：串 S 中任意个连续的字符组成的子序列叫中任意个连续的字符组成的子序列叫 S S 的子串的子串;主串主串：包含子串的串：包含子串的串 S 叫叫主串主串。字符位置字符位置：字符在串中的序号。：字符在串中的序号。子串位置子串位置：子串的第一个字符在主串中的序号。：子串的第一个字符在主串中的序号。串相等串相等：串长度相等，且对应位置上字符相等。：串长度相等，且对应位置上字符相等。例例1 1：现有以下：现有以下4 4个字符串：个字符串：a=BEI b=JING c=BEIJING d=BEI JING问：问：他们各自的长度？他们各自的长度？a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？空串是哪个串的子串？空串是哪个串的子串？a a是不是自己的子串？是不是自己的子串？a=3，b=4，c=7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1 1C C语言中已有类似串运算函数语言中已有类似串运算函数串的抽象数据类型定义串的抽象数据类型定义ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 基本操作基本操作:（教材（教材p71给出给出1313种基本操作种基本操作）StrAssign(&T,chars)/串赋值，生成值为串赋值，生成值为charschars的串的串T T StrCompare(S,T)/串比较，若串比较，若STST，返回值大于返回值大于00 StrLength(S)/求串长，即返回求串长，即返回S S的元素个数的元素个数 Concat(&T,S1,S2)/串连接，用串连接，用T T返回返回S1S1S2S2的新串的新串 SubString(&Sub,S,pos,len)/求求S S中中pospos起长度为起长度为lenlen的子串的子串 Index(S,T,pos)/返回子串返回子串T T在在pospos之后的位置之后的位置 Replace(&S,T,V)/用子串用子串V V替换子串替换子串T T4.1 4.1 串类型定义串类型定义最最最最小小小小操操操操作作作作子子子子集集集集注：注：ConcatConcat操作操作concatenationconcatenation，把多个短字符串合并为长字符串把多个短字符串合并为长字符串复习：复习：C语言中常用的串运算语言中常用的串运算4.1 4.1 串类型定义串类型定义注：用注：用C C处理字符串时，要调用标准库函数处理字符串时，要调用标准库函数#include串比较串比较：int strcmp(char*s1,char*s2);/StrCompare(S,T)求串长：求串长：int strlen(char*s);/StrLength(S)串连接：串连接：char strcat(char*to,char*from)/Concat(&T,S1,S2)子串子串T T定位：定位：char strchr(char*s,char*c);/Index(S,T,pos)4.1 4.1 串类型定义串类型定义可利用可利用串比较串比较、求串长和求子串等操作实现定、求串长和求子串等操作实现定位函数实现位函数实现Index(S，T，pos)算法的基本思想为：算法的基本思想为：StrCompare(SubString(S,i,StrLength(T),T)S 串串 T 串串 T 串串iposn-m+1n=StrLength(S)m=StrLength(T)4.1 4.1 串类型定义串类型定义算法描述：算法描述：int Index(String S,String T,int pos)/T为非空串。若主串为非空串。若主串S中第中第pos个字符之后存在与个字符之后存在与T T相等的子串，相等的子串，/则返回第一个这样的子串在则返回第一个这样的子串在S S中的中的 位置，否则返回位置，否则返回0 0 if(pos 0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/while/if return 0;/S中不存在与中不存在与T相等的子串相等的子串/IndexIndex(S,T,pos)/返回返回子串子串T T在主串在主串S S中第中第pospos之之后第一次出现的位置后第一次出现的位置例例1 1：设设 s=I AM A STUDENT,t=GOOD,q=WORKER。求：求：StrLength(s)StrLength(t)SubString(&sub,s,8,7)=SubString(&sub,t,2,1)=Index(s,A)=Index(s,t)=Replace(&s,STUDENT,q)=4.1 4.1 串类型定义串类型定义14 4STUDENTO30I AM A WORKER思考：思考：SubString(&sub,q,5,0)=长度为长度为 0 的子串为的子串为“合法合法”串串4.1 4.1 串类型定义串类型定义例例2 2：设设 s=I AM A STUDENT,t=GOOD,求：求：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)？解：因为解：因为SubString(s,6,2)A；SubString(s,7,8)STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以：所以：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)A GOOD STUDENT 4.2 4.2 串的表示和实现串的表示和实现4.24.2 串的表示和实现串的表示和实现串串的逻辑结构和的逻辑结构和线性表线性表极为相似，极为相似，区别区别仅在于仅在于串的串的数据对象约束为字符集。数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对作为操作对象；象；在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为操作对象。作为操作对象。例如查找某子串，在主串某位置上插入一个子串等。例如查找某子串，在主串某位置上插入一个子串等。4.24.2 串的表示和实现串的表示和实现定长顺序存储表示定长顺序存储表示定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列堆分配存储表示堆分配存储表示堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。但存储空间是在程序执行过程中动态分配而得。但存储空间是在程序执行过程中动态分配而得。但存储空间是在程序执行过程中动态分配而得。串的块链存储串的块链存储串的块链存储串的块链存储链式方式存储链式方式存储链式方式存储链式方式存储串有三种机内表示方法：串有三种机内表示方法：串有三种机内表示方法：串有三种机内表示方法：顺序顺序顺序顺序存储存储存储存储链式链式链式链式存储存储存储存储4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元来存放串值的字符序列。用一组地址连续的存储单元来存放串值的字符序列。为每个定义的变量分配为每个定义的变量分配固定长度固定长度存储区存储区#define MAXSTRLEN 255 /用户可在用户可在255以内定义最大串长以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度4.24.2 串的表示和实现串的表示和实现如：如：SStringSString x;x;x x是有是有256256个字符型变量的数组个字符型变量的数组 x0=5,x1=a,5 a H c d B .串的实际长度可在这个予定义长度的范围内随意设定，超过串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为予定义长度的串值则被舍去，称之为“截断截断”4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示1.串联接串联接Concat(&T,s1,s2)4.24.2 串的表示和实现串的表示和实现串的联接算法中需分三种情况处理串的联接算法中需分三种情况处理S10+S20MAXSTRLENS10 MAXSTRLEN,S10+S20MAXSTRLENS10=MAXSTRLENS1 sm s1 s2 S2 tn t1 t2 T sm+tn s1 s2 t1 t2 T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;4.24.2 串的表示和实现串的表示和实现 Status Concat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，/否则否则FALSE。return uncut;/Concat T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSTRSIZE)/截断 else /截断(仅取S1)T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示2.求子串求子串SubString(&Sub,S,pos,len)4.24.2 串的表示和实现串的表示和实现将串将串S S中从第中从第pospos个字符开始、长度为个字符开始、长度为lenlen的字符序列复制到串的字符序列复制到串SubSub中中(注：串注：串SubSub的预留长度与的预留长度与S S一样一样)s=a1 a2.anposlenSub 讨论：在操作中出现串值序列长度超过上界讨论：在操作中出现串值序列长度超过上界MAXSIZE时，约定截尾法处理。若想存放时，约定截尾法处理。若想存放超长超长字符串怎么办？字符串怎么办？改用改用动态分配动态分配的一维数组的一维数组堆堆4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示2.求子串求子串SubString(&Sub,S,pos,len)算法描述：算法描述：Status SubString(SString&sub,SString S,int pos,int len)if(posS0|lenS0-pos+1)return ERROR;/若若pospos和和lenlen参数越界，则告警参数越界，则告警 Sub1len=Spospos+len-1;Sub0=len;return OK;/4.24.2 串的表示和实现串的表示和实现子串长度子串长度4.24.2 串的表示和实现串的表示和实现4.2.2 4.2.2 堆分配存储表示堆分配存储表示仍用一组连续的存储单元来存放串，但存储空间是在程仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中序执行过程中动态分配动态分配而得。而得。通常，通常，C C语言中存在一个称之为语言中存在一个称之为“堆堆”的自由存储空间。提供的自由存储空间。提供的串类型就是以这种存储方式实现的。系统利用函数的串类型就是以这种存储方式实现的。系统利用函数malloc()和和free()进行串值空间的进行串值空间的动态管理。动态管理。/=串的堆分配存储表示串的堆分配存储表示=typedef struct char*ch;/若是非空串若是非空串,则按串实际长度分则按串实际长度分/配存储区配存储区;否则否则 ch为为NULL int length;/串长度串长度 HString;301 11 A b c d e 1 2 w r A B 301x.ch x.length4.24.2 串的表示和实现串的表示和实现4.2.2 4.2.2 堆分配存储表示堆分配存储表示串插入操作：串插入操作：void StrInsert(HString&S,int pos,HString T)/1posStrLength(S)1。在串在串 S S 的第的第 pos pos 个字符之前插入串个字符之前插入串 T Tif(posS.length+1)return ERROR;/pospos不合法则告警不合法则告警 if(T.length)/只要串只要串T T不空，就需要重新分配不空，就需要重新分配S S空间，以便插入空间，以便插入T T if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);for(i=S.length-1;i=pos-1;-i)/为插入为插入T T而腾出而腾出pospos之后的位置之后的位置 S.chi+T.length=S.chi;/从从S S的的pospos位置起全部字符均后移位置起全部字符均后移 S.chpos-1pos+T.length-2=T.ch0T.length-1;/插入插入T T S.length+=T.length;/刷新刷新S S串长度串长度 return OK;return OK;/StrInsert _HSqC C是指针变量，可以是指针变量，可以自增！意即每次后自增！意即每次后移一个数据单元。移一个数据单元。4.24.2 串的表示和实现串的表示和实现4.2.2 4.2.2 堆分配存储表示堆分配存储表示Status StrAssign(HString&T,char*chars)/生成一个串长量生成一个串长量chars的串的串T if(T.ch)free(T.ch);/释放释放T原有空间原有空间 for(i=0,c=chars;c;+i,+c);/求串长度求串长度if(!i)T.ch=NULL;T.length=0;else if(!(T.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);T.ch0.i-1=chars0.i-1;T.length=i;return OK;/StrAssign此处此处T.T.chch00没有用没有用来装串长，因为另来装串长，因为另有有T.length T.length 分量分量其它基本操作的算法描述见教材其它基本操作的算法描述见教材P77P774.24.2 串的表示和实现串的表示和实现4.2.3 4.2.3 串的块链存储表示串的块链存储表示由于串结构的特殊性由于串结构的特殊性结构中的每个数据元素是一结构中的每个数据元素是一个字符，则采用链表时，存在一个个字符，则采用链表时，存在一个结点大小结点大小问题问题。法法法法1 1 1 1：链表结点（数据域）大小取：链表结点（数据域）大小取：链表结点（数据域）大小取：链表结点（数据域）大小取1 1 1 1法法法法2 2 2 2：链表结点（数据域）大小取：链表结点（数据域）大小取：链表结点（数据域）大小取：链表结点（数据域）大小取n(n(n(n(例如例如例如例如n=4)n=4)n=4)n=4)A A B B C C I I NULLNULLheadheadheadheadA B C D A B C D E F G H E F G H I#NULLI#NULL最后结点未占满，补最后结点未占满，补“#”“#”或其它非串值字符或其它非串值字符4.24.2 串的表示和实现串的表示和实现4.2.3 4.2.3 串的块链存储表示串的块链存储表示存储密度存储密度=数据元素所占存储位数据元素所占存储位实际分配的存储位实际分配的存储位结点大小的选择直接影响着串处理效率结点大小的选择直接影响着串处理效率法法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；1/21/21/21/29/15=3/59/15=3/5存储密度小存储密度小(法法1)1)，运算处理方便，但占用存储量大，运算处理方便，但占用存储量大显然，若数据元素很多，用法显然，若数据元素很多，用法2 2存储更优存储更优称为称为块链块链结构结构目的：连结操作注意处理目的：连结操作注意处理第一个串尾无效字符第一个串尾无效字符4.24.2 串的表示和实现串的表示和实现4.2.3 4.2.3 串的块链存储表示串的块链存储表示块链类型定义：块链类型定义：#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE;/结点中的数据域结点中的数据域 struct Chunk*next;/结点中的指针域结点中的指针域 Chunk;typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head;/头指针头指针 Chunk *tail;/尾指针尾指针 int curLen;/结点个数结点个数 Lstring;/串类型只用一次，前面可以不加串类型只用一次，前面可以不加LstringLstring4.24.2 串的表示和实现串的表示和实现 a b c A B C 1#/块链结构存储示意图块链结构存储示意图 161head tail curlenX链式存储结构对某些操作链式存储结构对某些操作(如联接如联接)有一定方便之处有一定方便之处但总的来说不如另两种灵活，存储量大操作复杂。但总的来说不如另两种灵活，存储量大操作复杂。操作的实现和线性表类似，不作详细讨论。操作的实现和线性表类似，不作详细讨论。4.3 4.3 串的模式匹配算法串的模式匹配算法是各种串的处理系统中最重要的操作之一是各种串的处理系统中最重要的操作之一4.34.3 串的模式匹配算法串的模式匹配算法定义定义：子串的：子串的定位定位操作通常称为串的模式匹配。操作通常称为串的模式匹配。Index(S，T，pos)为典型函数：其中为典型函数：其中S称为主串，称为主串，T称为模式串。称为模式串。回忆：回忆：Index(S，T，pos)初始条件：初始条件：串串S和和T存在，存在，T是非空串，是非空串，1posStrLength(S)。操作结果：操作结果：若主串若主串 S 中存在和串中存在和串 T 值相同的子串返回它在主值相同的子串返回它在主串串 S 中第中第 pos 个字符之后第一次出个字符之后第一次出现现的位置的位置;否则函数值为否则函数值为0 0。教材教材P72 P72 算法算法4.1 4.1 用其它操作实现用其它操作实现4.34.3 串的模式匹配算法串的模式匹配算法下面讨论两种匹配算法：下面讨论两种匹配算法：一、简单算法一、简单算法Index(S,T,pos)二、改进算法二、改进算法KMPKMP算法算法4.34.3 串的模式匹配算法串的模式匹配算法简单算法简单算法 S 串 T 串 T 串iposn-m+1j算法设计思想：算法设计思想：将主串将主串S的第的第pos个字符和模式个字符和模式T的第的第1 1个字符比较，个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串，从主串S的下一字符的下一字符（pos+1）起，重新与起，重新与T第一个字符比较。第一个字符比较。i=pos,pos+1,n-m+1;j=1,2,m;直到主串直到主串S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T相等。返回值为相等。返回值为S中与中与T匹匹配的子序列配的子序列第一个字符第一个字符的序号，即匹配成功。的序号，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值0 0.4.34.3 串的模式匹配算法串的模式匹配算法简单算法简单算法例：主串例：主串s=ababcabcacbab 与模式与模式t=abcac的匹配过程。的匹配过程。第一趟第一趟：a b a b c a b c a c b a b a b c a c i=2j=2i=3j=3 第二趟第二趟：a b a b c a b c a c b a b a b c a ci=2j=14.34.3 串的模式匹配算法串的模式匹配算法简单算法简单算法 第三趟第三趟：a b a b c a b c a c b a b a b c a c i=3j=1i=4j=2i=6j=4i=5j=3i=7j=5 第四趟第四趟：a b a b c a b c a c b a b a b c a ci=4j=14.34.3 串的模式匹配算法串的模式匹配算法简单算法简单算法 第五趟第五趟：a b a b c a b c a c b a b a b c a ci=5j=1 第六趟第六趟：a b a b c a b c a c b a b a b c a ci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=64.34.3 串的模式匹配算法串的模式匹配算法简单算法简单算法算法描述：算法描述：int Index(SString S,SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。若不存在，个字符之后的位置。若不存在，/则函数值为则函数值为0。其中，。其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index相当于子串向右滑动一个字符位置相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置回的是被匹配的首个字符位置4.34.3 串的模式匹配算法串的模式匹配算法改进算法改进算法KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)改进改进：每一趟匹配过程中出现字符比较不等时，：每一趟匹配过程中出现字符比较不等时，不需回溯不需回溯 i i 指针（简单匹配算法指针（简单匹配算法i=i-j+2i=i-j+2），而是利用已经得到的而是利用已经得到的“部分部分匹配匹配”的结果，的结果，将模式串向右将模式串向右“滑动滑动”尽可能远的一段距离后，尽可能远的一段距离后，继续进行比较。继续进行比较。第三趟第三趟：a b a b c a b c a c b a b a b c a c i=3j=1i=4j=2i=7j=5i=6j=4i=5j=3 第一趟第一趟：a b a b c a b c a c b a b a b c a c i=2j=2i=3j=3 第二趟第二趟：a b a b c a b c a c b a b a b c a ci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5 第三趟第三趟：a b a b c a b c a c b a b （a）b c a ci=7j=2i=8j=3i=9j=4i=10j=5i=11j=6如何由当前部分匹配结果确定如何由当前部分匹配结果确定模式向右滑动的新比较起点模式向右滑动的新比较起点k k？KMP算法算法假设假设 主串为主串为“s1 s2 sn”，模式串为模式串为“p p1 p2 pm”，如在匹如在匹配配过程中产生过程中产生“失配失配”（si pj)，模式串应向右滑动多远，即模式串应向右滑动多远，即si 应与模式串的应与模式串的pj前面第几个字符再比较？前面第几个字符再比较？假设假设 si应与第应与第k(kj)个字符个字符pk继续比较，则模式中前继续比较，则模式中前k-1个字个字符必须满足下列关系：符必须满足下列关系：p1 p2 pk-1=si-k+1 si-k+2 si-1(1)而已得到的部分匹配结果是而已得到的部分匹配结果是：pj-k+1 pj-k+2 pj-1=si-k+1 si-k+2 si-1(2)由由(1)(1)、(2)(2)得到：得到：p1 p2 pk-1 =pj-k+1 pj-k+2 pj-1 4.34.3 串的模式匹配算法串的模式匹配算法S=a b a b c a b c a c b a bT=T=a b c a ci ik ki ik kj jS=a b a b c a b c a c b a bT=T=a b c a ci ij jS=a b a b c a b c a c b a bT=T=a b c a c4.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法若令若令nextj=k，则模式串的则模式串的next函数如下定义：函数如下定义：0 ,j=1 nextj=max k|1kj且且p1 pk-1 =pj-k+1 pj-1 1 ，其它其它j 1 2 3 4 5 6 7 8 模式串模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2 J 1 2 3 4 5 6 7 8 模式串模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2J=1 next1=0J=2 满足满足1kJ的的k不存在，不存在，next2=1J=3 满足满足1kJ的的k=2 p1=a不等于不等于p2=b,next3=1J=4 满足满足1kJ的的k=2，3；k=2:p1=a 等于等于 p3=a k=3:p1p2=ab不等于不等于p2p3=ba,next4=2J=5 满足满足1kJ的的k=2，3,4；k=2:p1=a 等于等于 p4=a k=3:p1p2=ab不等于不等于p3p4=aa,k=4:p1p2p3=aba不等于不等于p2p3p4=baa,next5=2J 1 2 3 4 5 6 7 8 模式串模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2J=6 满足满足1kJ的的k=2，3,4，5；k=2:p1=a 不等于不等于 p5=b k=3:p1p2=ab 等于等于 p4p5=ab,k=4：p1p2p3=aba不等于不等于 p3p4p5=aab,k=5:p1p2p3p4=abaa不等于不等于p2p3p4p5=baab。next6=3J=7 满足满足1kJ的的k=2，3,4，5，6；k=2:p1=a 不等于不等于 p6=c k=3:p1p2=ab 不等于不等于 p5p6=bc,k=4：p1p2p3=aba不等于不等于 p4p5p6=abc,k=5:p1p2p3p4=abaa不等于不等于p3p4p5p6=aabc,k=6:p1p2p3p4p5=abaab不等于不等于 p2p3p4p5p6=baabc,next7=1J 1 2 3 4 5 6 7 8 模式串模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2J=8 满足满足1kJ的的k=2，3,4，5，6，7；k=2:p1=a 等于等于 p7=a k=3:p1p2=ab 不等于不等于 p6p7=ca,k=4：p1p2p3=aba不等于不等于 p5p6p7=bca,k=5:p1p2p3p4=abaa不等于不等于p4p5p6p7=abca,k=6:p1p2p3p4p5=abaab不等于不等于 p3p4p5p6p7=aabca,k=7:p1p2p3p4p5p6=abaabc不等于不等于 p2p3p4p5p6p7=baabca,next8=2 简单匹配简单匹配 i=i-j+2,j=1;4.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法算法描述：算法描述：int Index_KMP(SString S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功匹配成功 else return 0;/Index_KMP过程示例见教材过程示例见教材P82 P82 图图4.54.54.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法如何求得模式串的如何求得模式串的next函数值？函数值？是一个是一个递推过程递推过程，分析如下，分析如下:已知：已知：next1=0；设：设：nextj=k，则存在如下关系：则存在如下关系：p1 p2 pk-1 =pj-k+1 pj-k+2 pj-1 此时：此时：nextj+1=？若若pk=pj，则表明：则表明：p1 p2 pk =pj-k+1 pj-k+2 pj，即即 nextj+1=nextj+1若若pk!=pj，则表明：则表明：p1 p2 pk！=pj-k+1 pj-k+2 pj，则则又是一个模式匹配问题。又是一个模式匹配问题。当当 pj!=pk时将模式串向右滑动让第时将模式串向右滑动让第j个字符和个字符和nextk 比较。若相等则比较。若相等则nextj+1=nextk+1,否则否则依依次类推次类推直至某次匹配相等或不等，如不等则直至某次匹配相等或不等，如不等则 nextj+1=1。4.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法 j 1 2 3 4 5 6 7 8模式模式 a b a a b c a c nextj 0 1 1 2 2 3 1 2 (a b a)(a)算法描述：算法描述：void get_next(SString&T,int&next )/求模式串求模式串T的的next函数值并存入数组函数值并存入数组next。i=1;next1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;/get_next例如：例如：4.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法nextnext函数存在缺点：函数存在缺点：分析：分析：例如模式例如模式aaaab与主串与主串aaabaaaab匹配时的情况匹配时的情况 T：a a a a bj：1 2 3 4 5 nextj：0 1 2 3 4S:a a a b a a a a b T:a a a a b i:1 2 3 4 5 6 7 8 9 a a a a ba a a a ba a a a ba a a a b此时效率不高的原因为：子串前此时效率不高的原因为：子串前4 4位相同时，主串字符若与位相同时，主串字符若与其中一个不相等，则不必再与其余其中一个不相等，则不必再与其余3 3个比较。而实际上还在个比较。而实际上还在依次比较依次比较4.34.3 串的模式匹配算法串的模式匹配算法KMP算法算法改进思想：改进思想：得到得到nextj=k，而模式中而模式中pj=pk，则当主串字符则当主串字符si和和pj比较不等时，不需要比较不等时，不需要再和再和pk比较，而直接和比较，而直接和pnextk比较，即此时比较，即此时nextj和和nextk相同。相同。j 1 2 3 4 5模式模式 a a a a bNextj 0 1 2 3 4Nextvalj 0 0 0 0 4 void get_nextval(SString&T,int&nextval)i=1;nextval1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else j=nextvalj;/get_nextvalS:a a a b a a a a b T:a a a a b i:1 2 3 4 5 6 7 8 9 a a a a b本章小结串串逻辑结构逻辑结构存储结构存储结构操作操作(或运算或运算)s=a1a2.an定长顺序存储构定长顺序存储构块链存储结构块链存储结构堆存储结构堆存储结构模式匹配算法模式匹配算法函数的实现函数的实现模式匹配即模式匹配即子串定位子串定位运算，即如何实现运算，即如何实现 Index(S,T,pos)函数函数一、简单算法一、简单算法二、二、KMPKMP算法算法