数据结构课件：串

串数据结构4.1串4.2串的存储结构4.3串基本操作的实现算法4.4串的模式匹配算法4.5本章小结在用计算机进行非数值处理问题时经常要用到串。串是一种线性结构。和线性表不同的是，串的操作特点是一次操作一个子串。串可以用顺序存储结构和链式存储结构存储。串的顺序存储结构空间效率和时间效率都更高。模式匹配是串最重要的一个操作。Brute-Force和KMP算法是两种最经常使用的串的模式匹配算法。

4.1.1串及其基本概念

串(也称作字符串)是由n(n≥0)个字符组成的有限序列。一般记作S＝"s0，s1，…，sn-1"，其中S称作串名，n称作串的长度，双引号括起来的字符序列称作串的值，每个字符si(0≤i<n)可以是任意的ASCII码字符，一般是字母、数字、标点符号等可在屏幕上显示的字符。4.1串一个串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。

一个字符在一个串中的序号(通常为大于等于0的正整数)称为该字符在串中的位置。可以比较任意两个串的大小。我们称两个串是相等的，当且仅当这两个串的值完全相等。两个串的值完全相等意味着两个串不仅长度相等，而且各个对应位置字符都相等。例如，下列串s1，s2，s3，s4和s5均不相等。前三个串首先长度就不相等，s3和s4虽然长度相等，但最后一个位置的字符不相等。

s1＝"Data"

s2＝"DataStructure"

s3＝"DataStructure"

s4＝"DataStructurs"

s5＝"datastructure"

要注意的是，26个字母字符有大写和小写之分，大写字母字符和小写字母字符有不同的ASCII码值，因此s3和s5不相等。在C语言中，表示一个串值时用一对双引号把串值括起来，但双引号本身不属于串，双引号的作用只是为了避免与变量名或数的常量混淆。

虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序列，而字符只是一个字符。因此即使是长度为1的串也和字符不同。例如串"a"和字符′a′(字符通常用单引号括起来)就是两个不同的概念。因为串"a"不仅要存储字符′a′，还要存储该串的长度数据；而字符′a′只需存储字符′a′，不需存储长度数据。

串在许多应用软件中都有应用。例如微软公司Word工具软件的操作对象就是用户输入或打开的串类型的文件。4.1.2串的抽象数据类型

1.数据集合

串的数据集合可以表示为字符序列s0，s1，…，sn-1，每个数据元素的数据类型为字符类型。

2.操作集合

为方便下边讨论中的示例，我们先定义如下几个串：

S1＝"Iamastudent"

S2＝"student"

S3＝"teacher"

S4＝"Iamateacher"

(1)赋值Assign(S，T)：把串T的值赋给串S。

(2)求长度Length(S)：求串S的长度。

例如，Length(S1)＝14，Length(S2)＝7。

(3)比较Compare(S，T)：比较串S和串T的ASCII码值的大小，若S等于T则函数返回0；若S大于T则函数返回1；若S小于T则函数返回-1。

例如，Compare(S4，S1)＝1。这是因为当比较到第7个字符时，有字符′t′的ASCII码值大于字符′s′的ASCII码值，所以函数返回1。

(4)插入Insert(S，pos，T)：若参数满足约束条件0≤pos<Length(S)，则在串S的第pos个字符前插入串T，串S的新长度为Length(S)＋Length(T)，函数返回1；若参数不满足约束条件，则函数返回0。例如，Insert(S1，4，"not")操作后，串S1＝"Iamnotastudent"。

(5)删除Delete(S，pos，len)：若参数满足约束条件0≤pos<Length(S)-1，1≤len和pos＋len≤Length(S)-1，则删除串S中从第pos个字符开始，长度为len的连续字符，且函数返回1；若参数不满足约束条件，则函数返回0。

例如，Delete(S1，6，7)操作后，串S1＝"Iama"。

(6)截取子串SubString(S，pos，len，T)：若参数满足约束条件0≤pos<Length(S)-1，1≤len和pos＋len≤Length(S)-1，则截取串S中从第pos个字符开始，长度为len的连续字符并赋给串T，且函数返回1；若参数不满足约束条件，则函数返回0。

例如SubString(S1，6，7，T)操作后，串T＝"student"。

(7)查找Search(S，start，T)：在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则函数返回子串T在主串S中的第一个字符位置；若主串S中不存在子串T，则函数返回-1。

例如，Search(S1，0，S2)＝7，Search(S1，0，S3)＝-1。

(8)替换Replace(S，start，T，V)：在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。

例如，Replace(S1，0，S2，S3)的返回值为1，且该函数调用后，S1＝"Iamateacher"。

对比串的抽象数据类型和线性表的抽象数据类型可以发现，两者的数据集合非常类同，差别仅是串的数据元素类型限定为字符类型。换句话说，串的数据集合是线性表数据集合限定为字符类型的特例。但两者的操作集合差别却很大。两者的操作集合的最大不同是，线性表中的操作是以“一个数据元素”作为操作对象的，而串中的操作是以“一个串”作为操作对象的。4.1.3C语言的串函数

C语言用字符数组存储串。串的长度是不定的，C语言解决串的长度不定的方法是在串的末尾自动添加一个字符′＼0′作为串结束标志。下面的语句定义了一个字符数组并赋初值"DataStructure"：

Charstr［］＝"DataStructure";

串"DataStructure"在内存中的存储形式如下：

这样，数组名str就指示了串"DataStructure"在内存中的首地址，结束标志′＼0′就指示了串的结束。

C语言的库文件string.h中提供了许多实现串操作的函数。C语言中提供的实现串操作的函数功能和我们在4.1.2节讨论的串操作的功能不完全相同。几个常用的C语言串函数及其使用方法如下(各次示例都从定义语句开始)。

假设我们已有如下定义语句：chars1［］＝"Iamastudent";

chars2［20］＝"teacher";

chars3［］＝"student";

intresult;

chars4［20］，*p;1)串长度intstrlen(char*str)printf("%d＼n"，strlen(s1));/*输出14*/

printf("%d＼n"，strlen(s2));/*输出7*/

2)拷贝char*strcpy(char*str1，char*str2)strcpy(s4，s2);

printf("%s＼n"，s4);/*输出teacher*/3)比较intstrcmp(char*str1，char*str2)

result＝strcmp(s2，s3);/*s2>s3*/

printf("%d＼n"，result);/*输出1*/

result＝strcmp(s2，s2);/*s2＝＝s3*/

printf("%d＼n"，result);/*输出0*/

result＝strcmp(s3，s2);/*s3<s2*/

printf("%d＼n"，result);/*输出-1*/

4)字符定位char*strchr(char*str，charch) p＝strchr(s1，′s′);/*p指在s1中字符′s′的位置*/

printf("%s＼n"，p);/*输出student*/

5)子串查找char*strstr(char*s1，char*s2) p＝strstr(s1，s3);/*p指在s1中字符′s′的位置*/

printf("%s＼n"，p);/*输出student*/

6)连接char*strcat(char*str1，char*str2)strcat(s2，s3);

printf("%s＼n"，s2);/*输出teacherstudent*/

C语言提供的实现串操作的函数功能较强，但由于函数定位通常用字符指针，所以使用的难度较大。下面是一个使用C语言提供的串函数编程的例子。

【例4-1】名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。设计算法设计：因为C语言自动在串末尾添加结束标志′＼0′，所以实现方法是：首先把原姓名串name的空格改写为′＼0′(注意此时结束标记′＼0′后边，即指针p＋1指示的，是原姓名串name的姓部分；此时的原姓名串name表示的是原来姓名的名部分)；然后把原姓名串name的姓部分、逗号和名部分分步添加到新姓名串newName中，最后再恢复原姓名串name为开始时的状态。

程序如下：＃include<string.h>

＃include<stdio.h>

voidReverseName(char*name，char*newName)

{

char*p;

p＝strchr(name，′′);/*p指在空格′′位置*/

*p＝′＼0′;/*把空格换为′＼0′，因此name的长度只包括名部分*/

strcpy(newName，p＋1);/*指针p＋1指示的是原姓名串name的姓部分*/

strcat(newName，"，");/*新姓名串newName等于姓＋逗号*/

strcat(newName，name);/*新姓名串newName等于姓＋逗号＋名*/

*p＝′′;/*恢复原姓名串name为开始时的状态*/

}

voidmain(void)

{

charname［］＝"WilliamTopp"，newName［30］;

ReverseName(name，newName);

printf("ReverseName：%s"，newName);

}程序运行如下：

Topp，William

串的存储结构有顺序存储结构和链式存储结构两种。由于串的顺序存储结构不仅各种操作实现方便，而且空间效率和时间效率都更高，因此更为常用。4.2串的存储结构4.2.1串的顺序存储结构

和线性表的顺序存储结构类似，可用一个字符类型的数组存放串值。用数组存储串时，当定义了一个串变量，这个串在内存中的开始地址就确定了。但由于串的长度是不确定的，因此需要有某种方法确定一个串的长度。

串是不定长的，在串的顺序存储结构中，表示串的长度通常有两种方法：一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程；另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。例如，C语言定义串为字符类型的数组(即顺序存储结构)，串值是双引号中的字符序列，系统将自动在串值的末尾添加结束标记′＼0′字符(字符′＼0′为ASCII代码0，亦即空操作字符。这样，字符数组名给出了串在内存中的开始地址，串值末尾的结束标记'＼0'标记了串在内存中的结束位置。当自己定义串的顺序存储结构时，设置串的长度参数确定串的长度的方法更为常用。为了算法实现方便，或为了兼容两种串的长度表示方法，也可同时使用两种方法来表示串的长度。

串的顺序存储结构就是用数组存放串的所有字符，数组有静态数组和动态数组两种，因此，串的顺序存储结构也有静态数组结构和动态数组结构两种。

1.静态数组结构

串的静态数组结构也称为定长数组结构，因为此时数组的长度是编译时确定的，在运行时是不可改变的。串的静态数组结构体可定义如下：typedefstruct

{

charstr［MaxSize］;

intlength;

}String;其中，MaxSize表示数组的最大存储空间，str表示存储串值的数组名，length表示串的长度(必须满足length<MaxSize)，String是为结构体定义的名字。

2.动态数组结构

动态数组亦即数组的元素个数在用户使用时确定。一般情况下，系统从一个称为堆栈的区域为用户定义的动态数组分配存储单元。串的动态数组结构体可定义如下：typedefstruct

{

char*str;

intmaxLength;

intlength;

}

DString;其中，str表示动态数组的首地址(亦即数组名)，maxLength表示动态数组的最大数组元素个数，length表示当前串的长度(必须满足length≤maxLength)，DString是为结构体定义的名字。我们在2.3.1节已说过，C语言提供了动态申请和释放内存空间的函数。其中两个主要的函数是malloc()函数和free()函数。malloc()函数也可用于动态数组的申请，并返回所申请动态数组内存单元的首地址。free()函数也可用于释放动态数组存储单元。

malloc()函数和free()函数用于动态数组申请和动态数组释放的一个例子如下：

＃include<malloc.h>

＃include<string.h>

voidmain(void)

{

intlength＝100;/*length为动态数组的元素个数*/

char*str，s1［］＝"DataStructure";

str＝(char*)malloc(sizeof(char)*length);/*动态数组申请*/

strcpy(str，s1);/*把s1的串值赋给str*/

free(str);/*动态数组释放*/

}4.2.2串的链式存储结构

串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据域上。串的链式存储结构有单字符结点链和块链两种。

1.单字符结点链

单字符结点链就是每个结点的数据域只包括一个字符。单字符结点链的结构体定义如下：typedefstructNode

{

charstr;

structNode*next;

}

SCharNode;在上述结构体定义中，每个字符域str所占的存储空间为1个字节，而每个指针域next所占的存储空间为2个或3个(根据机器不同而不同)字节。显然，单字符结点链的空间利用效率非常低。

2.块链

块链就是每个结点的数据域包括若干个字符。块链的结构体定义如下：typedefstructNode

{

charstr［Number］;

structNode*next;

}NCharNode;其中，Number为每个结点数据域的字符个数。当Number数值比较大时，块链的空间利用效率比单字符结点链的空间利用效率要高很多。当Number数值比较大时，块链的空间利用效率和串的顺序存储结构的空间利用效率接近。

前面我们已指出，串的顺序存储结构是串较为常用的存储结构。本节主要讨论串在静态数组存储结构下几个典型操作的实现算法。串的静态数组结构体定义为：4.3串基本操作的实现算法

typedefstruct

{

charstr［MaxSize］;

intlength;

}String;下面给出串的静态数组结构下几个操作的实现算法。

1.插入操作intInsert(String*S，intpos，StringT)

/*在串S的pos位置插入子串T*/

{

inti;

if(pos<0)

{

printf("参数pos出错！");

return0;

}

elseif(S->length＋T.length>MaxSize)

{

printf("数组空间不足无法插入！");

return0;

}

else

{

for(i＝S->length-1;i>＝pos;i--)

S->str［i＋T.length］＝S->str［i］;/*为插入做准备*/

for(i＝0;i<T.length;i＋＋)

S->str［pos＋i］＝T.str［i］;/*插入*/S->length＋＝T.length;/*产生新的长度值*/

return1;

}

}

对比上述串的插入操作和第2章讨论的线性表的插入操作可以发现，两个算法十分相似，只是串的插入操作一次插入了T->length个字符，而线性表的插入操作一次插入了1个数据元素。

2.删除操作intDelete(String*S，intpos，intlen)

/*删除串S从pos位置开始长度为len的子串值*/

{

inti;

if(S->length<＝0)

{

printf("数组中未存放字符无元素可删!＼n");

return0;

}

elseif(pos<0||len<0||pos＋len>S->length)

{

printf("参数pos和len不合法");

return0;

}

else

{

for(i＝pos＋len;i<＝S->length-1;i＋＋)

S->str［i-len］＝S->str［i］;/*依次前移*/

S->length-＝len;/*产生新的长度值*/

return1;

}

}

对比上述串的删除操作和第2章讨论的线性表的删除操作可以发现，两个算法十分相似，只是串的删除操作一次删除了len个字符，而线性表的删除操作一次删除了1个数据元素。

3.取子串操作intSubString(StringS，intpos，intlen，String*T)

/*取串S从pos位置开始长度为len的子串值赋给串T*/

{

inti;

if(pos<0||len<0||pos＋len>S.length)

{

printf("参数pos和len出错");

return0;

}

else

{

for(i＝0;i<len;i＋＋)

T->str［i］＝S.str［pos＋i］;/*给子串T赋值*/

T->length＝len;/*给子串T的长度域赋值*/

return1;

}

}对比上述串的取子串操作和第2章讨论的线性表的取数操作可以发现，两个算法十分相似，只是取子串操作一次取了len个字符，而线性表的取数操作一次取了1个数据元素。

串的动态数组结构体定义为：typedefstruct

{

char*str;

intmaxLength;

intlength;

}DString;下面给出串的动态数组结构下插入操作的实现算法。intInsert(DString*S，intpos，DStringT)

/*在串S的pos位置插入子串T*/

{

inti;

char*p;

if(pos<0)

{

printf("参数pos出错！");

return0;

}

else

{

if(S->length＋T.length>S->maxLength)

{

p＝(char*)realloc(S->str，(S->length＋T.length)*sizeof(char));

if(p＝＝NULL)

{

printf("内存空间不足！");

return0;

}

}

for(i＝S->length-1;i>＝pos;i--)

S->str［i＋T.length］＝S->str［i］;/*为插入做准备*/

for(i＝0;i<T.length;i＋＋)

S->str［pos＋i］＝T.str［i］;/*插入*/

S->length＋＝T.length;/*产生新的元素个数*/

return1;

}

}对比动态数组结构下的插入操作算法和静态数组结构下的插入操作算法可以发现，在动态数组结构下，当判断插入后空间不足时，可以给主串S重新分配内存空间后插入子串，而不是像静态数组结构下出错返回。

函数realloc()的原型是：

(void*)realloc(void*p，unsignedsize)

函数realloc()的功能是将p所指向的已分配内存区的大小改为size，函数返回新分配内存区的首地址。size既可以比原来分配的内存区大，也可以比原来分配的内存区小。新分配内存区中原样保存原内存区中的数据值。当新分配的内存区size2小于原内存区的size1时，新分配内存区中原样保存原内存区中前size2个数据值。

很多学生会对上述串操作的调用方法感到困难，尤其会对动态数组存储结构下的串操作的调用方法感到困难，下面的例4-2将给出两个简单示例。

【例4-2】设串分别采用静态数组存储结构和动态数组存储结构，串s1＝"Data"，串s2＝"Structure"，要求编写程序实现把串s1插入到串s2的0位置，并显示串s2中的字符。设计(1)设静态数组存储结构下串抽象数据类型的实现文件为"SString.h"，静态数组存储结构下的程序如下：＃include<stdio.h>

＃defineMaxSize100

＃include"SString.h"

voidmain(void)

{

StringmyString1＝{"Data"，5}，

myString2＝{"Structure"，9};

inti;

Insert(&myString2，0，myString1);

for(i＝0;i<myString1.length;i＋＋)

printf("%c"，myString1.str［i］);

}

(2)设动态数组存储结构下串抽象数据类型的实现文件为"DString.h"，动态数组存储结构下的程序如下：＃include<stdio.h>

＃include<malloc.h>

＃include<string.h>

＃include"DString.h"

voidmain(void)

{

DStringmyString1，myString2;

inti;

myString1.str＝(char*)malloc(sizeof(char)*10);

myString2.str＝(char*)malloc(sizeof(char)*20);

strcpy(myString1.str，"Data");

strcpy(myString2.str，"Structure");

myString1.length＝5;

myString1.maxLength＝10;

myString2.length＝9;

myString2.maxLength＝20;

Insert(&myString2，0，myString1);

for(i＝0;i<myString2.length;i＋＋)

printf("%c"，myString2.str［i］);

printf("＼n");

}

两个程序运行后的输出结果均为：

DataStructure

串抽象数据类型中讨论的查找操作也称作串的模式匹配操作。模式匹配操作的具体含义是：在主串(也称作目标串)S中，从位置start开始查找是否存在子串(也称作模式串)T，4.4串的模式匹配算法如在主串S中查找到一个与模式串T相同的子串，则函数返回模式串T的第一个字符在主串S中的位置；如在主串S中未查找到一个与模式串T相同的子串，则函数返回-1。

本节讨论的串均采用顺序存储结构，因此，这里所说的一个字符在一个串中的位置亦即一个字符在一个串中的数组下标。Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。4.4.1Brute-Force算法

Brute-Force算法实现模式匹配的思想是：从主串s＝"s0s1…sn-1"的第一个字符开始和模式串t＝"t0t1…tm-1"的第一个字符比较，若相等则继续比较后续字符；否则从主串s的第二个字符开始重新与模式串t的第一个字符比较，若相等则继续比较后续字符；否则从主串s的第三个字符开始重新与模式串t的第一个字符比较；如此继续下去，若模式串t中的每个字符依次和主串s中的一个连续字符序列相等，则匹配成功，函数返回模式串t的第一个字符在主串s中的下标；若比较完主串s的所有字符序列，不存在一个和模式串t相等的子串，则匹配失败，函数返回-1。

图4-1模式匹配过程为便于理解，举例说明如下。设主串s＝"cddcdc"，模式串t＝"cdc"，s的长度为n＝6，t的长度为m＝3，用变量i指示主串s当前比较字符的下标，用变量j指示模式串t当前比较字符的下标。模式匹配过程如图4-1所示。

从上述匹配过程我们可以推知两点：

(1)若在前k-1次比较中未匹配成功，则第k次比较是从s中的第k个字符sk-1开始和t中的第一个字符t0比较。

(2)设某一次匹配有si≠tj，其中0≤i<n，0≤j<m，i≥j，则应有si-1＝tj-1，…，si-j＋1＝t1，si-j＝t0。再由(1)知，下一次比较主串的字符si-j＋1和模式串的第一个字符t0。

因此，模式匹配的一般性过程如图4-2所示。

图4-2模式匹配的一般性过程根据上面的分析，可设计模式匹配的Brute-Force算法如下：typedefstruct

{

charstr［Maxlength］;

intlength;

}String;/*顺序存储结构的串结构体定义*/

intBFIndex(StringS，intstart，StringT)

/*查找主串S从start开始的子串T，找到则返回T在S中的开始字符下标，否则返回-1*/

{

inti＝start，j＝0，v;

while(i<S.length&&j<T.length)

{

if(S.str［i］＝＝T.str［j］)

{

i＋＋;

j＋＋;

}

else

{

i＝i-j＋1;

j＝0;

}

}

if(j＝＝T.length)v＝i-T.length＋1;

elsev＝-1;

returnv;

}这个算法简单且易于理解，但有些情况下时间效率不高。主要原因是：在主串和子串已有相当多个字符经比较相等的情况下，只要有一个字符比较不相等，便需要把主串的比较位置(即算法中变量i的值)回退。设主串的长度为n，子串的长度为m，则Brute-Force算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符刚好等于模式串的m个字符；Brute-Force算法在最坏情况下的时间复杂度为O(n*m)。

Brute-Force算法的最坏情况分析如下：当模式串的前m-1个字符序列和主串的相应字符序列比较总是相等，但模式串的第m个字符和主串的相应字符比较总是不等，此时，模式串的m个字符序列必须和主串的相应字符序列块一共比较n-m＋1次，每次比较m个字符，总共约需比较m*(n-m＋1)次，因此其时间复杂度为O(n*m)。如s＝"aaaaaaaa"，t＝"aab"，n＝8，m＝3，t的前2个字符序列和s的相应字符序列比较总是相等，t的第3个字符和s的相应字符比较总是不等，t的3个字符序列和s的相应字符序列块一共比较了n-m＋1＝6次，每次比较了3个字符，最后又比较了两个字符，即比较了s6＝t0＝′a′，s7＝t1＝′a′，当j＝2，i＝8时，因循环条件不满足而退出循环，所以总共比较了m*(n-m＋1)＋2＝3*6＋2＝20次。4.4.2KMP算法

KMP算法是三位学者在Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute-Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等，但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退，从而可以大大提高效率。

分析Brute-Force算法的匹配过程可以发现，算法中的主串比较位置的回退并非一定必要。这可分两种情况，第一种情况是模式串中无真子串(关于模式串中的真子串的讨论将在后面进行)，如图4-1所示的主串s＝"cddcdc"，模式串t＝"cdc"的模式匹配过程，当s0＝t0，s1＝t1，s2≠t2时，算法中下一次的比较位置为i＝1，j＝0，即接下来比较s1和t0。但是因t0≠t1，而s1＝t1，所以一定有s1≠t0。所以此时比较s1和t0无意义，实际上随后可直接比较s2和t0。

第二种情况是模式串中有真子串，设主串s＝"abacabab"，模式串t＝"abab"，第一次匹配过程如图4-3所示。此时有s0＝t0＝′a′，s1＝t1＝′b′，s2＝t2＝′a′，s3≠t3。因有t0≠t1，s1＝t1，所以必有s1≠t0。又因有t0＝t2，s2＝t2，所以必有s2＝t0，因此接下来可直接比较s3和t1。

图4-3模式匹配例子总结以上两种情况可以发现，一旦si和tj比较不相等时，主串s的比较位置不必回退，主串的si(或si＋1)可直接和模式串的tk(0≤k<j)比较，k的确定与主串s并无关系，k的确定只与模式串t本身的构成有关，即从模式串本身就可求出k的值。

现在我们讨论一般情况。设s＝"s0s1…sn-1"，t＝"t0t1…tm-1"，当模式匹配比较到si≠tj(0≤i<n，0≤j<m)时，必存在

(4-1)我们再来讨论关于模式串中的真子串问题。我们把模式串中从第一个字符位置开始到任一个字符位置j为止的模式串中的真子串定义为如下的next［j］函数：此时若模式串中不存在可相互重叠的真子串，则说明在模式串"t0t1…tj-1"中不存在任何以t0为首字符的字符串与主串"si-jsi-j＋1…si-1"中分别以si-j，si-j＋1，…，si-1为首字符的字符串匹配，下一次可直接比较si和t0，这是第一种情况。

此时若模式串中存在可相互重叠的真子串，满足

(4-2)

则说明模式串中的子串"t0t1…tk-1"已和主串"si-ksi-k＋1…si-1"匹配，下一次可直接比较si和tk，这是第二种情况。

(4-3)

next［j］函数定义的第一种情况即是模式串中存在其子串的情况，其他两种情况是模式串中不存在其子串的情况。其中next［0］＝-1是为方便算法设计定义的。

当模式串t中的tj与主串s的si(i≥j)比较不相等时，若模式串t中不存在如上所述的真子串，有next［j］＝0，则下一次比较si和t0，这是第一种情况；若模式串t中存在真子串"t0t1…tk-1"＝"tj-ktj-k＋1…tj-1"，且满足0<k<j，则有next［j］＝k，next［j］＝k表示的是随后和主串s的si比较的子串t的字符为tk，这是第二种情况；当j＝0时令next［j］＝-1，此处-1为一标记，在next［j］＝-1时令随后比较si＋1和t0。

KMP算法的模式匹配过程如图4-4所示，当模式串t中存在真子串"t0t1…tk-1"＝"tj-ktj-k＋1…tj-1"时，若模式串t中的tj与主串s的si比较不相等，我们此时可将模式串t按照k＝next［j］的值右滑。模式串t右滑后若仍有si≠tk，则模式串t按照新的k＝next［j］的值继续右滑，这样的过程可一直进行到k＝next［j］＝-1时为止，k＝next［j］＝-1时模式串t不再右滑，随后比较si＋1和t0。

图4-4KMP算法的模式匹配过程总结以上的讨论，KMP算法的思想是：设s为主串，t为模式串，设i为主串s当前比较字符的位置，j为模式串t当前比较字符的位置，令i和j的初值为0。当si＝tj时，i和j分别增1再继续比较；否则i不变，j改变为等于next［j］再继续比较。依此类推，直到下列两种情况之一：一是j退回到某个j＝next［j］时有si＝tj，则i和j分别增1再继续比较；二是j退回到j＝-1，此时令主串和模式串的位置各增1，再继续比较。这样的循环过程直到变量i大于等于S.length或变量j大于等于T.length结束。KMP算法可设计如下：typedefstruct

{

charstr［Maxlength］;

intlength;

}String;/*顺序存储结构的串结构体定义*/

intKMPIndex(StringS，intstart，StringT，intnext［］)

/*查找主串S从start开始的子串T，找到则返回T在S中的开始字符下标，否则返回-1*/

/*数组next中存放有模式串T的next［j］值*/

{

inti＝start，j＝0，v;

while(i<S.length&&j<T.length)

{

if(j＝＝-1||S.str［i］＝＝T.str［j］)

{

i＋＋;

j＋＋;

}

elsej＝next［j］;

}

if(j＝＝T.length)v＝i-T.length＋1;

elsev＝-1;

returnv;

}我们再来讨论求next［j］的算法问题。从计算next［j］值的公式(4-3)可以看出，next［j］值的计算问题是一个递推计算问题。设有next［j］＝k，即在模式串t中存在"t0t1…tk-1"＝"tj-ktj-k＋1…tj-1"(0<k<j)，其中k为满足等式的最大值，则计算next［j＋1］的值有两种情况：

(1)若tk＝tj，则表明在模式串t中有"t0t1…tk"＝"tj-ktj-k＋1…tj"，且不可能存在任何一个k′>k满足上式，因此有

next［j＋1］＝next［j］＋1＝k＋1

(2)若tk≠tj，则可把计算next［j＋1］值的问题看成是一个如图4-5所示的模式匹配问题，即把模式串t′向右滑动至k′＝next［k］(0<k′<k<j)，若tk′＝tj，则表明在模式串t中有"t0t1…tk'"＝"tj-k′tj-k′＋1…tj"(0<k′<k<j)，因此有

next［j＋1］＝k′＋1＝next［k］＋1

图4-5求next［j＋1］的模式匹配若tk′≠tj，则将模式串t′继续右滑到k″＝next［k′］。依此类推，直到某次匹配成功或k＝-1，k＝-1时有

next［j＋1］＝next［0］＋1＝-1＋1＝0此种情况的举例说明见例4-4。

因此，可有类同模式匹配的KMP算法的求子串的next［j］值的算法如下：voidGetNext(StringT，intnext［］)

/*求子串T的next［j］值并存于数组next中*/

{

intj＝0，k＝-1;

next［0］＝-1;/*递推的初始值*/

while(j<T.length)

{

if(k＝＝-1||T.str［j］＝＝T.str［k］)

{

j＋＋;

k＋＋;

next［j］＝k;

}

elsek＝next［k］;

}

}下边我们给出求next［j］的几个例子。

计算t＝"aba"的next［j］。

当j＝0时，next［0］＝-1；

当j＝1时，next［1］＝0；当j＝2时，t0≠t1，next［2］＝0。

即有

【例4-3】计算t＝"abcabcaaa"的next［j］。

当j＝0时，next［0］＝-1；

当j＝1时，next［1］＝0；当j＝2时，t0≠t1，next［2］＝0；

当j＝3时，t0≠t2，next［3］＝0；

当j＝4时，t0＝t3＝′a′，next［4］＝1；

当j＝5时，t1＝t4＝′b′，即有t0t1＝t3t4＝"ab"，next［5］＝next［4］＋1＝1＋1＝2；

当j＝6时，t2＝t5＝′c′，即有t0t1t2＝t3t4t5＝"abc"，next［6］＝next［4］＋1＝2＋1＝3；当j＝7时，t3＝t6＝′a′，即有t0t1t2t3＝t3t4t5t6＝"abca"，next［7］＝next［6］＋1＝3＋1＝4；

当j＝8时，t4≠t7，k＝next［k］＝next［4］＝1，因t1≠t7，k＝next［k］＝next［1］＝0；因t0＝t7＝′a′，next［8］＝next［1］＋1＝0＋1＝1。这也就是计算next［j＋1］值时的第二种情况。

即有

4.4.3Brute-Force算法和KMP算法的比较

本节我们用两个实际例子比较Brute-Force算法和KMP算法的实际比较次数。

编程比较Brute-Force算法和KMP算法的实际比较次数，两个实际例子为：

(1)S＝"cddcdc"，T＝"cdc";

(2)S＝"aaaaaaaa"，T＝"aab"。

设计设计思想：分别把Brute-Force算法和KMP算法改造为返回累计比较次数，然后在主函数中分别用两个实际例子参数调用改造过的Brute-Force算法和KMP算法，最后输出两个算法对实际例子的实际比较次数值。程序设计如下：＃include<stdio.h>

＃defineMaxlength100

typedefstruct

{

charstr［Maxlength］;

intlength;

}String;

intBFIndexC(StringS，intstart，StringT)

{

inti＝start，j＝0，v;

v＝0;/*比较次数赋初值*/

while(i<S.length&&j<T.length)

{

if(S.str［i］＝＝T.str［j］)

{

i＋＋;

j＋＋;

}

else

{

i＝i-j＋1;

j＝0;

}

v＋＋;/*比较次数加1*/

}

returnv;/*返回比较次数*/

}

voidGetNext(StringT，intnext［］)

{

intj＝0，k＝-1;

next［0］＝-1;

while(j<T.length)

{

if(k＝＝-1||T.str［j］＝＝T.str［k］)

{

j＋＋;

k＋＋;

next［j］＝k;

}

elsek＝next［k］;

}

}

intKMPIndexC(StringS，intstart，