《数据结构》串》PPT课件.ppt

1、第第4 4章章 串串4.1串及其操作串及其操作 4.2串的存储结构串的存储结构4.3串的基本运算实现串的基本运算实现 4.4串的模式匹配运算串的模式匹配运算 习题习题 在非数值处理的应用领域中，字符串的应用非常广泛。在非数值处理的应用领域中，字符串的应用非常广泛。如编辑器如编辑器(Edit、Word本质上是字符串处理本质上是字符串处理)、信息检索、信息检索(字字符串比较符串比较)等。等。实际上，编写数值计算程序的机会很有限。从发明计实际上，编写数值计算程序的机会很有限。从发明计算机的思路来说，其目的是为了模拟人类的对信息的逻辑算机的思路来说，其目的是为了模拟人类的对信息的逻辑处理方法，而数值计

2、算仅仅是一种逻辑思路的标准化。处理方法，而数值计算仅仅是一种逻辑思路的标准化。现今我们使用的计算机的硬件结构主要反映数值计算的现今我们使用的计算机的硬件结构主要反映数值计算的需要的，因此，在处理字符串数据时比处理整数和浮点数需要的，因此，在处理字符串数据时比处理整数和浮点数要复杂的多。而且，在不同类型的应用中，所处理的字符要复杂的多。而且，在不同类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须串具有不同的特点，要有效地实现字符串的处理，就必须根据具体情况使用合适的存储结构。下面将讨论字符串的根据具体情况使用合适的存储结构。下面将讨论字符串的一些处理方法和字符串的几种

3、不同的存储结构。一些处理方法和字符串的几种不同的存储结构。4.1 串及其操作串及其操作 4.1.1 串的逻辑结构串的逻辑结构 定义：定义：串串(字符串字符串)，是由零个或多个字符组成的有限序，是由零个或多个字符组成的有限序列。一般记作：列。一般记作：s=a0a1an-2an-1 (n0)s是串的名。是串的名。双引号括双引号括起来是是串的值。起来是是串的值。n为串的长度。为串的长度。空串空串为零个字符，为零个字符，n=0。子串子串为串中任意个连续的字符组成的子序列。为串中任意个连续的字符组成的子序列。位置位置为字符在序列中的序号。为字符在串中的称作。为字符在序列中的序号。为字符在串中的称作。子串

4、位置子串位置以子串的第一个字符在主串中的位置来表示。以子串的第一个字符在主串中的位置来表示。举例：举例：a=This is a string 串长串长=16 b=string串长串长=6，是，是a的子串，在的子串，在a串的位置是串的位置是10 c=串长串长=2，的空格串，它不是，的空格串，它不是a和和b的子串。的子串。串的集合定义：串的集合定义：设设string=(D，R)是一个数据结构，其中是一个数据结构，其中 D=a0，a1，an-1 为字符元素的集合，为字符元素的集合，i=0，n-1，并且，并且n0。R=|ai-1，aiD，i=1，2，n-1 R为上元素的关系集合为上元素的关系集合 则称

5、则称 string是一个字符串。字符串与线性表的区别是是一个字符串。字符串与线性表的区别是 它的数据对象为字符集。它的数据对象为字符集。4.1.2 串的基本运算串的基本运算 (1)赋值操作赋值操作assign(s，t)。将。将t的值赋给的值赋给s。(2)串相等判断串相等判断equal(s，t)函数。若函数。若s串与串与t串相等，则函数串相等，则函数返回返回1，否则函数将返回，否则函数将返回0。(3)串的联接操作串的联接操作concat(s，t)函数。将函数。将s串和串和t串联接成一串联接成一个串，新生成的串是个串，新生成的串是s串在前，而串在前，而t串紧接串紧接s串的尾部。串的尾部。例如，设例

6、如，设a=data,b=structure,执行执行concat(a,b),新生成的串是新生成的串是data structure。串的联接不满足交换律串的联接不满足交换律:concat(s,t)!=concat(t,s);串的联接满足结合律串的联接满足结合律:concat(s1，concat(s2，s3)=concat(s1，s2，s3)其运算结果是将这其运算结果是将这3个串的值依次首尾相接得到一个新串。个串的值依次首尾相接得到一个新串。(4)求长度求长度length(s)函数。其函数值为串函数。其函数值为串s中字符的个数。中字符的个数。(5)求子串求子串sub(s，start，len，t)。

7、若。若 0startlength(s)0lenlength(s)-start则则t中值为从串中值为从串s中第中第start个字符起，长度为个字符起，长度为len的字符序列，的字符序列，并且函数返回值为并且函数返回值为1；否则函数返回值为；否则函数返回值为0。例如，例如，s=data structure,sub(s，5，5，t),则则 t=struc。(6)子串定位子串定位index(s,t)函数。若在主串函数。若在主串s中存在和中存在和t相等的相等的子串，则函数值为子串，则函数值为s中第一个这样的子串在主串中第一个这样的子串在主串s中的位置，中的位置，否则函数值为否则函数值为-1。注意，在此。

8、注意，在此t不能是个空串。例如，不能是个空串。例如，s=data structure，t=ru,则则index(s,t)=7。(7)替换替换replace(s,t,v)。操作结果是以串。操作结果是以串v替换串替换串s中出现中出现的所有和非空子串的所有和非空子串t相同的不重叠子串。相同的不重叠子串。4.2 串的存储结构串的存储结构 在程序执行的过程中，串的值可变。所以，与在在程序执行的过程中，串的值可变。所以，与在程序出现的其他类型的变量一样，给要处理的串赋程序出现的其他类型的变量一样，给要处理的串赋一个变量名，这样在对串进行操作时，可以通过变一个变量名，这样在对串进行操作时，可以通过变量名访其

9、值。量名访其值。串的存储结构有两种形式：串的存储结构有两种形式：一种是将串设计成一种结构类型，串是字符型一种是将串设计成一种结构类型，串是字符型的数组，从串名可直接访问到串值，串值的存储分的数组，从串名可直接访问到串值，串值的存储分配是在编译时完成；配是在编译时完成；一种是串值的存储分配是在程序运行时完成，在一种是串值的存储分配是在程序运行时完成，在串名和串值之间需要建立一个对照表，这个对照表串名和串值之间需要建立一个对照表，这个对照表称之为串名的存储映像。称之为串名的存储映像。4.2.1 顺序存储结构顺序存储结构 用一组地址连续的存储单元存储串字符序列。唯一确用一组地址连续的存储单元存储串字

10、符序列。唯一确定一个串，需要二个数据：串的起始地址，串的长度。在定一个串，需要二个数据：串的起始地址，串的长度。在C语言中，对字符串处理两个要素是：数组名，结束标记语言中，对字符串处理两个要素是：数组名，结束标记符号，如图符号，如图4.1所示所示 ch datastr ucture001234567891011121314n-1 图4.1串的顺序存储结构 说明：说明：ch是一个数组，存放串是一个数组，存放串”data structure”，判断串的，判断串的结束标志为字符结束标志为字符0，在它前面的字符组成串。在这种表，在它前面的字符组成串。在这种表示方法中，访问子串方便，但插入、删除麻烦，需

11、要大量示方法中，访问子串方便，但插入、删除麻烦，需要大量移动字符。例如，要取子串移动字符。例如，要取子串 sub(s,5,4,t)，只要将数组，只要将数组ch5到到ch8赋给赋给t，便可实现求子串运算。，便可实现求子串运算。顺序存储结构又分为非紧缩格式和紧缩格式。顺序存储结构又分为非紧缩格式和紧缩格式。a.非紧缩格式非紧缩格式 一个存储单元存放一个字符。若计算机的存储单元是一个存储单元存放一个字符。若计算机的存储单元是按字编址，并且计算机字长大于八位二进制数，这样，在按字编址，并且计算机字长大于八位二进制数，这样，在一个存储单元仅仅存放一个字符就浪费存储空间，但简化一个存储单元仅仅存放一个字符

12、就浪费存储空间，但简化了对串的操作。例如，在一个字长为了对串的操作。例如，在一个字长为32位的计算机中，其位的计算机中，其一个存储单元为四个字节，但只存放一个字符一个存储单元为四个字节，但只存放一个字符(字符只占一字符只占一个字节个字节)，所以空间浪费，如图，所以空间浪费，如图4.2所示。所示。b.紧缩格式紧缩格式 图图4.3紧缩格式为了节省存储空间，也可以用紧缩方紧缩格式为了节省存储空间，也可以用紧缩方式，即在一个存储单元中存放多个字符，如图式，即在一个存储单元中存放多个字符，如图4.3所示，在所示，在一个存储单元中存放一个存储单元中存放4个字符。显然，紧缩格式可以节省个字符。显然，紧缩格式

13、可以节省空间，但在对串值进行访问时需要花费较多时间分离同一空间，但在对串值进行访问时需要花费较多时间分离同一存储单元中字符。存储单元中字符。da ta s t ruc tu re图4|2 非紧缩格式 d a t a s t ru c t ur e图4.3紧缩格式 实际使用：实际使用：如果计算机采用以字节为如果计算机采用以字节为存储单元，一个字符占用一个存储单存储单元，一个字符占用一个存储单元元(字节字节)，此时既节省空间，处理又，此时既节省空间，处理又方便，方便，C语言中字符串存储采用该方语言中字符串存储采用该方法，即图法，即图4.1所示，在后面讨论的串运所示，在后面讨论的串运算，都采用这种存

14、储结构算，都采用这种存储结构（字符数组（字符数组）。4.2.2 链式存储结构链式存储结构 用链表方式存储串值。由于串结构的特殊性，即结构用链表方式存储串值。由于串结构的特殊性，即结构中每一个数据元素是一个字符，用链表存储串值时，结点中每一个数据元素是一个字符，用链表存储串值时，结点的大小需要讨论的大小需要讨论每个结点是存放一个字符，还是存放每个结点是存放一个字符，还是存放多个字符。例如，图多个字符。例如，图4.4所示是结点大小分别为存放所示是结点大小分别为存放4个字个字符和符和1个字符。个字符。(a)结点大小为4的链表(b)结点大小为1的链表 图4.4结点大小不同的链表 4.2.3 堆存储结构

15、堆存储结构 堆结构是一种动态存储结构。系统将一个容量很大的堆结构是一种动态存储结构。系统将一个容量很大的连续空间作为多个串值可共用的空间，每当建立一个新串连续空间作为多个串值可共用的空间，每当建立一个新串时，若该串尚未赋值，它不占堆的存储空间；若要给该串时，若该串尚未赋值，它不占堆的存储空间；若要给该串赋值，首先，从未分配的堆空间中分配给该串值要求的空赋值，首先，从未分配的堆空间中分配给该串值要求的空间，然后，将串值写入到分配的空间中；同样，当串的值间，然后，将串值写入到分配的空间中；同样，当串的值无意义或串值被赋空串时，原串值所占用的空间要还给堆。无意义或串值被赋空串时，原串值所占用的空间要

16、还给堆。所以，串的存储地址是动态分配的，一个串值的确定是通所以，串的存储地址是动态分配的，一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名和过串在堆中的起始位置和串的长度实现的。为此，串名和串值之间要建立一个对照表串值之间要建立一个对照表。例如图例如图4.5，所示为对照表和，所示为对照表和存放字符串的堆。存放字符串的堆。串名起址串长0123456789 A 0 4datastruct B 4 9urebookfree=17 C 13 4 (a)对照表对照表 (b)堆堆store的状态的状态 图图4.5 堆存储结构堆存储结构在图中假定，堆是一个字符数组，在图中假定，堆是一个字符

17、数组，定义定义为：为：char storeMAX；/*存放串值的堆，存放串值的堆，MAXMAX表示连续空间最大容量表示连续空间最大容量*/int free；/*free free为当前可分配空间起始地址的指针，起初值为为当前可分配空间起始地址的指针，起初值为0 0*/在堆中存放的三个串分别是：在堆中存放的三个串分别是：a=data b=structure c=book 4.3 串的基本运算实现串的基本运算实现 字符串是一种特殊的线性表，对它的操作不同于对线字符串是一种特殊的线性表，对它的操作不同于对线性表的处理，有自己独特的处理方法。在实际串的处理中，性表的处理，有自己独特的处理方法。在实际串

18、的处理中，其存储结构为字符数组。下面讨论在这种存储方式下的串其存储结构为字符数组。下面讨论在这种存储方式下的串的运算。的运算。定义：定义：#define MAX 100 /*MAX MAX为数组最大下标为数组最大下标 */char tMAX,sMAX;/*s,t s,t为存放字符串的数组为存放字符串的数组 */(1)算法算法4.1 求字符串长度函数求字符串长度函数length(s)。int length(char s)/*求串求串s s的长度的长度 */int i;for(i=0,si!=0；i+)；return(i)；(2)算法算法4.2求子串函数求子串函数substr(s,start,le

19、n,t)int sub(char s,int start,int len,char t)/*若若0startlength(s0startlength(s)并且并且0lenlength(s)-start0lenlength(s)-start，则，则将串将串s s中从第中从第startstart个字符起，长度为个字符起，长度为lenlen的字符序列复制到的字符序列复制到t t中，函中，函数返回数返回1 1；否则函数返回；否则函数返回0 0*/int n,i;if(start=(n=length(s)return(0);if(lenn)return(0);for(i=0;i=MAX)return(0

20、);for(i=0;in;i+)sm+i=ti;ti=0;/*联接得到串的结束标志联接得到串的结束标志 */return(1);(4)算法算法4.4 串相等判断函数串相等判断函数equal(s,t)int equal(char s,char t)/*若若s s串与串与t t串相等，则函数返回串相等，则函数返回1 1，否则函数将返回，否则函数将返回0 0*/int m,n,i;m=length(s);n=length(t);if(m!=n)return(0);for(i=0;im;i+)if(si!=ti)return(0);return(1);另外，在另外，在C语言的库函数中已经包含了一些串操

21、作函语言的库函数中已经包含了一些串操作函数，例如，赋值函数数，例如，赋值函数strcpy，判断函数，判断函数strcmp，求长度函，求长度函数数strlen，求子串，求子串substr等，在程序设计中可以直接调用。等，在程序设计中可以直接调用。4.4 串的模式匹配运算串的模式匹配运算 模式匹配：模式匹配：子串定位运算子串定位运算index(s,t,start)，即在主串，即在主串s中寻找子串中寻找子串t的过程通常称作串的模式匹配的过程通常称作串的模式匹配(其中其中t称为称为模式模式)。当匹配成功时当匹配成功时:index(s,t,start)函数的值为函数的值为t在在s中的序号；中的序号；当匹

22、配失败时，当匹配失败时，index(s,t,start)函数的返回值为函数的返回值为-1。为增加通用性，定义了一个为增加通用性，定义了一个start用来表示在用来表示在s中开始中开始匹配的字符位置。例如，匹配的字符位置。例如，s=abcdef，t=cde index(s，t，0)=2 s=abcdef，t=ab index(s，t，0)=0 s=abcdef，t=ad index(s，t，0)=-1 4.4.1 BF算法算法(Brute-Force)算法的基本思想：算法的基本思想：在主串在主串s中取从第中取从第i(i的初值的初值为为start)个字符起，并且长度和串个字符起，并且长度和串t相等

23、的子串和相等的子串和t比较，若相等，则求得函数值为比较，若相等，则求得函数值为i，否则，否则i增增1直至直至串串s中不存在从中不存在从i开始和开始和t相等的子串为止，匹配失相等的子串为止，匹配失败，返回败，返回-1。例如，主串例如，主串s为为ababcabcacbab 模式串模式串t为为abcac 匹配过程如图匹配过程如图4.6所示所示 s=a b a b c a b c a c b ab 取i=0开始子串subch!=ti=0t=a b c a c 匹配失败，i=i+1=1s=a b a b c a b c a c b ab 取i=1开始子串subch!=ti=1 t=a b c a c 匹

24、配失败，i=i+1=2s=a b a b c a b c a c b ab“取i=2开始子串subch!=ti=2 t=a b c a c 匹配失败，i=i+1=3s=a b a b c a b c a c b ab 取i=3开始子串subch!=ti=3 t=a b c a c 匹配失败，i=i+1=4s=a b a b c a b c a c b ab 取i=4开始子串subch!=ti=4 t=“a b c a c 匹配失败，i=i+1=5s=a b a b c a b c a c b ab 取i=5开始子串subch=ti=5 t=a b c a c 匹配成功，返回i=5 图4.6 取

25、子串的匹配过程 算法算法4.5 取子串进行比较的模式匹配算法。取子串进行比较的模式匹配算法。int index(char s,char t,int start)int i,eq,m,n;char subchMAX;m=strlen(s);n=strlen(t);if(startm)return(-1);/*起始点起始点+模式串长度模式串长度主串长度主串长度 */*subchsubch为在为在s s中从中从i i开始与开始与t t相同长度子串相同长度子串*/i=start;eq=sub(s,i,n,subch)；while(eq)if(strcmp(t,subch)break;/*i i开始的子

26、串与开始的子串与t t相等相等 */else i+;eq=sub(s,i,n,subch);/*从从i i开始的子串与开始的子串与t t不相等不相等*/if(eq)return(i);else return(-1);有回溯的模式匹配算法：有回溯的模式匹配算法：设置两个指针设置两个指针i和和j分别指分别指向主串向主串s和模式串和模式串t中当前正待比较的字符位置。中当前正待比较的字符位置。算法的基本思想是：算法的基本思想是：初始初始 i=0；j=0;做循环做循环 若若 si=tj 则则(继续逐个比较后续字符继续逐个比较后续字符i+,j+)否则否则,从主串的第二个字符起在重新和模式串比从主串的第二个

27、字符起在重新和模式串比较较(i返回到原位置加返回到原位置加1，j返回返回0).直至模式串直至模式串t的每一个字符依次和主串的每一个字符依次和主串s的一个连续的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。的字符序列相等，则称匹配成功，否则称匹配失败。该算法与前面所讨论的算法相同，只是前者是该算法与前面所讨论的算法相同，只是前者是以每一个位置为始点，取出子串与以每一个位置为始点，取出子串与t比较，而后是以比较，而后是以每一个位置为出发点，与每一个位置为出发点，与t比较，并且若匹配成功比比较，并且若匹配成功比较到较到t串结束，否则只需要比较到某一位置，即串串结束，否则只需要比较到某一位置，

28、即串s与与串串t的字符不相同。的字符不相同。i=2 s2!=t2 匹配失败第一趟匹配s=a b a b c a b c a c b a b i=0开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=2 i=1 s1!=t0 匹配失败第二趟匹配 s=a b a b c a b c a c b a b i=1开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=0 i=6 s6!=t4 匹配失败第三趟匹配 s=a b a b c a b c a c b a b i=2开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=4 例如主串例如主串s为为abab

29、cabcacbab，模式串，模式串t为为abcac，匹配，匹配过程如图过程如图4.7所示所示 i=3 s3!=t0 匹配失败第四趟匹配s=a b a b c a b c a c b a b i=3开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=0 i=4 s4!=t20 匹配失败第五趟匹配s=a b a b c a b c a c b a b i=4开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=0 i=10 j等于t的串长，匹配成功第六趟匹配s=a b a b c a b c a c b a b i=5开始t=a b c a c 返回i=i-n j=5

30、 图4.7BF算法的匹配过程算法算法4.6 有回溯的模式匹配算法。有回溯的模式匹配算法。int index(char s,char t,int start)int i,j,m,n;m=length(s);n=length(t);if(startm)return(-1);i=start;j=0;while(im&jn)if(si=tj)i+;j+;/*si=tj si=tj，比较下一个，比较下一个 */else /*si!=tj si!=tj */i=i-j+1;j=0;/*sitj sitj，i i回到原位置回到原位置+1+1，j j回到回到0 0*/if(jn)return(i-n);els

31、e return(-1);上面所描述的算法中，若从某一个上面所描述的算法中，若从某一个si开始与开始与tj比较比较(j=0)，若若si=tj，则，则i和和j后移；若后移；若si!=tj，j回到原位置回到原位置0，而，而i回到原位置加回到原位置加1。因为。因为j已经从原来的位置向后移动了已经从原来的位置向后移动了j次，次，所以所以i也向后移动了也向后移动了j次，故次，故i的原位置为的原位置为i-j，而原位置加，而原位置加1为为i-j+1。同样，当匹配成功时，函数值返回。同样，当匹配成功时，函数值返回i的原位置，这时的原位置，这时j从从0移动到串移动到串t的结束的结束(j=n)，即，即j向后移动向

32、后移动n次，同样，次，同样，i也也应向后移动了应向后移动了n次，所以，函数返回值是次，所以，函数返回值是i-n。这种有回溯的模式匹配算法在一些情况下，效率非常低，这种有回溯的模式匹配算法在一些情况下，效率非常低，例如，例如，s=aaaaaaab 串长为串长为n t=aab 串长为串长为m，并且，并且nm 这样，每趟比较这样，每趟比较m次后匹配失败，次后匹配失败，i回到原位置加回到原位置加1，j返返回到回到0，继续下一趟匹配，继续下一趟匹配,共计需要共计需要n-m趟。所以最坏情况趟。所以最坏情况下的时间复杂度为：下的时间复杂度为：O(n-m)*m)=O(n*m)，其原因是由每，其原因是由每次匹配

33、失败，次匹配失败，i回溯到原位置加回溯到原位置加1造成，下面我们讨论无回造成，下面我们讨论无回溯的模式匹配算法。溯的模式匹配算法。4.4.2 无回溯的模式匹配算法无回溯的模式匹配算法(KMP算法算法)算法的思想：算法的思想：是在每一趟匹配过程中，当出现是在每一趟匹配过程中，当出现si不等于不等于tj时，时，i不需要回溯到原位置加不需要回溯到原位置加1(i保持不变保持不变)，而是利用已经得到的，而是利用已经得到的“部分匹配部分匹配”的结果将模式串向右的结果将模式串向右“滑动滑动”尽可能远的一尽可能远的一段距离后，继续进行比较。段距离后，继续进行比较。i=6 s6!=t4 匹配失败第三趟匹配s=a

34、 b a b c a b c a c b a b i=2开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=4 例如，有回溯的匹配算法图例如，有回溯的匹配算法图4.7，在该算法的第三趟匹，在该算法的第三趟匹配中，当配中，当i=6和和j=4字符不等时字符不等时(si!=tj)，再次从，再次从i=3和和j=0重重新开始比较。但是，经仔细观察可以发现，在新开始比较。但是，经仔细观察可以发现，在s3和和t0，s4和和t0以及以及s5和和t0这三次比较都是不必进行的。这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中第因为从第三趟部分匹配的结果就可得出，主串中第4、5和

35、和6个字符必然是个字符必然是b、c和和a(即模式串中第即模式串中第2、3和和4个字个字符符)，而模式串的第一个字符是，而模式串的第一个字符是a，因此它无需再和这三，因此它无需再和这三个字符进行比较，仅需要将模式串指针个字符进行比较，仅需要将模式串指针j向右滑动到第二向右滑动到第二个字符的位置个字符的位置(i保持不变保持不变)继续进行继续进行i=6和和j=1时的字符比时的字符比较即可。较即可。i=2 s2!=t2 匹配失败第一趟匹配s=a b a b c a b c a c b a b i=0开始t=a b c a c i=i-j+1;j=0;进入下一趟 j=2 同理，在第一趟匹配中，从同理，在

36、第一趟匹配中，从i=0和和j=0开始进行比较，当开始进行比较，当比较到比较到i=2和和j=2字符不等时字符不等时(si!=tj)，i=6保持不变，而保持不变，而j滑滑动到动到j=0的位置继续进行字符的比较。如图的位置继续进行字符的比较。如图4.8所示，在整个所示，在整个匹配过程中匹配过程中,i指针没有回溯。指针没有回溯。i=2 s2!=t2 匹配失败第一趟匹配 s=a b a b c a b c a c b a b i=0开始t=a b c a c i=2不动;j滑动到 0 j=2 i=2 i=6 s6!=t4 匹配失败第一趟匹配 s=a b a b c a b c a c b a b i=0

37、开始t=a b c a c i=6不动;j滑动到1 j=0 j=4 i=6 i=10j等于t的串长，匹配成功第一趟匹配 s=a b a b c a b c a c b a b i=0开始t=a b c a c 返回i=i-n j=1 j=5图4.8 无回溯算法的匹配过程例如主串例如主串s为为ababcabcacbab，模式串，模式串t为为abcac，无回，无回溯的匹配过程如图溯的匹配过程如图4.8所示。所示。现在讨论一般情况。每趟匹配失败，根据子串现在讨论一般情况。每趟匹配失败，根据子串t的特性使的特性使i不回溯，这时不回溯，这时j退到恰当的某个位置重新比较。退到恰当的某个位置重新比较。设主串

38、为设主串为s0s1sn-1，模式串为，模式串为t0t1tm-1，从主，从主串串s中某一个位置开始比较，当匹配过程中产生中某一个位置开始比较，当匹配过程中产生“失失配配”(即即si!=tj)时，指针时，指针i应保持不变，如何设置应保持不变，如何设置j(si应与模式应与模式串中的哪个串中的哪个tj字符比较字符比较)?此时应有：此时应有：t0t1tj-1=si-jsi-j+1si-1 (4-1)假设此时假设此时j应滑动到应滑动到j=k(kk(即即si和和tk进行比较进行比较)，那么，那么k具有以下性质：具有以下性质：t0t1tk-1=si-ksj-k+1si-1 (4-2)同时利用已经得到的同时利用

39、已经得到的“部分匹配部分匹配”结果表达式结果表达式(4-1)可知，可知，这时应有：这时应有：tj-ktj-k+1tj-1=si-ksj-k+1si-1”(4-3)再从表达式再从表达式(4-2)和和(4-3)可得到，于是对可得到，于是对k的要求是：的要求是：t0t1tk-1=tj-ktj-k+1tj-1 (4-4)通俗说法是：当模式中通俗说法是：当模式中tj与主串中与主串中si失配时，将失配时，将si与与tk比较，比较，所取所取k的原则：模式串的前的原则：模式串的前k个字符子串等于个字符子串等于tj前的前的k个字符个字符子串，并且是具有此性质的最大子串的串长。如图子串，并且是具有此性质的最大子串

40、的串长。如图4.9所示。所示。图4.9 模式串的特征 反之，若模式串中存在满足反之，若模式串中存在满足(4-4)的两个子串，则当匹配过程的两个子串，则当匹配过程中，主串中第中，主串中第i个字符与模式串中第个字符与模式串中第j个字符比较不等时，仅个字符比较不等时，仅需要将模式串向右滑动至模式串中第需要将模式串向右滑动至模式串中第k个字符和主串中第个字符和主串中第i个个字符对齐，此时，模式串中头字符对齐，此时，模式串中头k个字符的子串个字符的子串t0t1tk-1必必定与主串中第定与主串中第i个字符之前长度为个字符之前长度为k的子串的子串si-ksj-k+1si-1相等。相等。如在图如在图4.8中，

41、当第二趟匹配中，当第二趟匹配“失配失配”时，时，i=6不变，不变，此时在模式串此时在模式串t0到到tj-1(即即t3)中，满足此性质的最中，满足此性质的最大子串为大子串为a，所以，所以k取取1，即从，即从i=6和和j=1进行第三进行第三趟匹配。在模式串中，对于不同的趟匹配。在模式串中，对于不同的tj有不同的有不同的tk，于是设一个数组于是设一个数组nextj=k，用于存储各字符，用于存储各字符tj的对的对应应tk的的k值。具体求值。具体求nextj的原则若下：的原则若下：(1)j=0时，时，nextj=-1。(2)存在存在t0t1tk-1=tj-ktj-k+1tj-1(0kj)，则，则 取取k

42、的最大值。的最大值。(3)否则，否则，nextj=0。j 0 1 2 3 4 5 6 模式串 a a a a a a bNextj-1 0 1 2 3 4 5 j 0 1 2 3 4 5 6 模式串 a a a a a a bNextj-1 0 1 2 3 4 5例例4.1例例4.2 因为next数组只与模式串相关，所以可以预先求出。假设假设next已经求得，则已经求得，则KMP的模式匹配算法用的模式匹配算法用C语言描述下：语言描述下：算法算法4.8 KMP的模式匹配算法。的模式匹配算法。int index_kmp(char s,char t,int next)/*从主串从主串s s起始位置开

43、始查找起始位置开始查找 */int i=0,j=0,m,n;m=strlen(s);n=strlen(t);while(im&j=n)return(i-n);else return(-1);求求next的算法又是如何实现的？的算法又是如何实现的？由定义可知：由定义可知：next0=-1设设 nextj=k，这表明在模式串中，这表明在模式串中 t0t1tk-1”=”tj-ktj-k+1tj-1其中其中k为满足为满足0kk满满足上式。此时足上式。此时nextj+1=?可能有两种情况：可能有两种情况：(1)若若tk=tj，则表明在模式串中，则表明在模式串中 t0t1tk-1tk=tj-ktj-k+1

44、tj-1tj并且，不可能存在并且，不可能存在kk满足上式，这就是说满足上式，这就是说nextj+1=k+1，即，即 nextj+1=nextj+1 (2)若若tk!=tj，则表明在模式串中，则表明在模式串中 t0t1tk-1tk!=tj-ktj-k+1tj-1tj 此时可以把求此时可以把求next数组问题看成是一个模式匹配问题，数组问题看成是一个模式匹配问题，整个模式串既是主串又是模式串，而当前在匹配过程中，整个模式串既是主串又是模式串，而当前在匹配过程中，已有已有t0=tj-k，t1=tj-k+1，tk-1=tj-1，则当，则当tk!=tj时应将时应将模式串向右滑动以至于使模式串中第模式串向

45、右滑动以至于使模式串中第k=nextk个字符和主个字符和主串中的第串中的第j个字符比较，若个字符比较，若tk=tj，则说明在主串中第，则说明在主串中第j+1个个字符前存在一个长度为字符前存在一个长度为k+1的最长子串，和模式串中头的最长子串，和模式串中头k+1个字符组成的子串相等，即个字符组成的子串相等，即 t0t1tk-1tk!=tj-ktj-k+1tj-1tj这就是说这就是说 nextj+1=k+1，即，即 nextj+1=nextk+1同理，若同理，若tk!=tj，则将模式继续向右滑动直至将模式中第，则将模式继续向右滑动直至将模式中第k=nextk个字符和个字符和tj对齐，对齐，依次类推

46、，直至，依次类推，直至tj和模和模式中某个字符匹配成功或者不存在任何式中某个字符匹配成功或者不存在任何k(0kj)满足等式满足等式t0t1tk-1tk!=tj-ktj-k+1tj-1tj，则，则 nextj+1=0 例如，模式串例如，模式串t=abaabcac，如图，如图4.10所示，已求得前所示，已求得前6个字符的个字符的next值，现在要求值，现在要求next6，因为，因为next5=2，又又t5!=t2，则需要比较，则需要比较t5和和t1(因为因为next2=0),这相当于将这相当于将子串模式向右滑动。由于子串模式向右滑动。由于t5!=t0，而且因，而且因next0=-1，所，所以以ne

47、xt6=0；又由；又由next6=0，并且，并且t6=t0，则，则next7=next6+1=1。通过上面分析，可得求。通过上面分析，可得求next值算值算法如下。法如下。j 0 1 2 3 4 5 6 7模式串模式串 a b a a b c a cnextjnextj-1 0 0 1 1 2 0 1 算法算法4.9 求求next数组算法。数组算法。get_next(char t,int next,int n)int j,k;j=0;k=-1;next0=-1;while(jn)if(k=-1)|tj=tk)j+;k+;nextj=k;else k=nextk;例例4.1 子串替换是字符串结构

48、的常用算法。它将主串子串替换是字符串结构的常用算法。它将主串s中所中所有和模式串有和模式串t相等的子串用新串相等的子串用新串v替换。要实现该算法，显替换。要实现该算法，显然要进行多次模式匹配，以定位和然要进行多次模式匹配，以定位和t相等的子串位置。在定相等的子串位置。在定位之后，进行字符替换时，应考虑以下三种情形：位之后，进行字符替换时，应考虑以下三种情形：(1)若若t的长度小于的长度小于v的长度，则主串的长度，则主串s需要扩充。需要扩充。(2)若若t和和v的长度相等，为简单替换。的长度相等，为简单替换。(3)若若t的长度大于的长度大于v的长度，则主串的长度，则主串s需要缩减。需要缩减。算法算

49、法4.7 利用模式匹配算法实现子串替换运算利用模式匹配算法实现子串替换运算/*s为主串，为主串，t模式串，模式串，v为新串为新串 */void substr(char s,char t,char v)int s_len,t_len,v_len,s_i,t_i,v_i,gap,i,j;s_len=length(s);t_len=length(t);v_len=length(v);gap=v_len-t_len;/*gap gap为新串和模式串的长度差为新串和模式串的长度差 */for(s_i=0;s_i+t_len=s_len;)for(t_i=0;s_is_len&t_i=t_len)/*位模

50、式串定位成功，以下是三种字符替换位模式串定位成功，以下是三种字符替换 */if(gap0)/*扩充扩充s s串串gapgap个单元，留意移位操作的方向个单元，留意移位操作的方向 */for(i=s_len-1;i=s_i;i-)si+gap=si;if(gap0)/*缩减缩减s s串串gapgap个单元，留意移位操作的方向个单元，留意移位操作的方向 */for(i=s_i;i=s_len-1;i+)si+gap=si;for(i=s_i-t_len,j=0;jv_len;i+,j+)si=vj;s_len=s_len+gap;/*调整调整ss的长度的长度 */s_i=s_i+gap;/*为下次