数据结构：第四章 串

1、1第第4章章 串（串（特殊的线性表特殊的线性表） 4.1串类型的定义串类型的定义 4.2串的表示和实现串的表示和实现 4.3串的模式匹配算法串的模式匹配算法 4.4串操作的应用举例串操作的应用举例本章要点l理解并掌握串的相关概念理解并掌握串的相关概念l掌握串的存储结构及其基本运算的实现掌握串的存储结构及其基本运算的实现l掌握掌握BF算法和算法和KMP算法的基本思想及模式匹配过算法的基本思想及模式匹配过程程 l灵活运用串的特点解决复杂的应用问题灵活运用串的特点解决复杂的应用问题难点：难点： KMP算法的基本思想及模式匹配过程算法的基本思想及模式匹配过程 重点：重点： 1、串的相关概念、串的相关概

2、念 2、串的存储结构及其基本运算的实现、串的存储结构及其基本运算的实现 3、KMP算法的基本思想及模式匹配过程算法的基本思想及模式匹配过程 本章要点：本章要点：34.1 4.1 串类型的定义串类型的定义1 1、串：？、串：？2 2、子串、主串：？、子串、主串：？3 3、串相等：？、串相等：？4 4、空格串：？、空格串：？5 5、串的抽象数据类型定义：？、串的抽象数据类型定义：？6 6、串的基本操作：？、串的基本操作：？44.1 4.1 串类型的定义串类型的定义1 1、串、串（或（或字符串字符串） 54.1 4.1 串类型的定义串类型的定义2 2、子串、主串、子串、主串子串子串主串主串例如例如注

3、意注意：空串是任意串的子串，任一串是它自身的：空串是任意串的子串，任一串是它自身的子串。除它本身外，一个串的其它子串都是它的子串。除它本身外，一个串的其它子串都是它的真子串真子串64.1 4.1 串类型的定义串类型的定义2 2、子串、主串、子串、主串子串子串主串主串字符在串中的位置字符在串中的位置子串在串中的位置子串在串中的位置例如例如74.1 4.1 串类型的定义串类型的定义3 3、串相等、串相等例如例如84.1 4.1 串类型的定义串类型的定义4 4、空格串、空格串思考：思考：1 1、空串和空格串的区别、空串和空格串的区别2 2、串与线性表的区别、串与线性表的区别94.1 4.1 串类型的

4、定义串类型的定义空串和空格串的区别：空串和空格串的区别：空串是长度为零的串，空空串是长度为零的串，空格串是仅包含空格字符的串，长度不为零。格串是仅包含空格字符的串，长度不为零。串与线性表的区别：串与线性表的区别：（1 1）数据对象数据对象: :串的数据对象约束为字符集串的数据对象约束为字符集（2 2）串的操作串的操作: :线性表大多以线性表大多以“单个元素单个元素”作为作为操作对象；串通常以操作对象；串通常以“串的整体串的整体”作为操作对象。作为操作对象。104.1 4.1 串类型的定义串类型的定义5 5、串的抽象数据类型定义、串的抽象数据类型定义ADT String 数据对象：数据对象：D

5、=aD =ai i | a | ai iCharacterset,(i=1,2,n, n0)Characterset,(i=1,2,n, n0)数据关系：数据关系：R1 = R1 = a ai-1i-1,a,ai i|a|ai-1i-1,a,ai i D,(i=2,3,n) D,(i=2,3,n) 基本操作：基本操作： StrAssign (&T, chars) StrCopy (&T, S) StrAssign (&T, chars) StrCopy (&T, S) StrEmpty (S) StrCompare (S, T) StrEmpty (S) StrCompare (S, T) S

6、trLength(S) ClearString(&S) StrLength(S) ClearString(&S)Concat (&T, S1, S2) SubString (&Sub, S, pos, len)Concat (&T, S1, S2) SubString (&Sub, S, pos, len)Index(SIndex(S，T T，pos) pos) Replace(&S, T,V)Replace(&S, T,V)StrInsert(&SStrInsert(&S，pospos，T) StrDelete (&S, pos, len) T) StrDelete (&S, pos, le

7、n) DestroyString(&S) DestroyString(&S) ADT String 114.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作1 1） StrAssign (&T, chars) 初始条件：初始条件：chars 是字符串常量。是字符串常量。 操作结果：操作结果：把把 chars 赋为赋为 T 的值。的值。2 2） StrCopy (&T, S)初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：由串由串 S 复制得串复制得串 T。124.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作 3） DestroySt

8、ring (&S)DestroyString (&S) 初始条件：初始条件：串串 S 存在。存在。 操作结果：操作结果：串串 S 被销毁。被销毁。4 4） StrEmptyEmpty (S)初始条件：初始条件：串串 S 存在。存在。操作结果：操作结果：若若 S S 为空串，则返回为空串，则返回truetrue， 否则返回否则返回 falsefalse。134.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作 5） StrCompare (S, T)StrCompare (S, T) 初始条件：初始条件：串串 S和和T存在。存在。 操作结果：操作结果：若若S T，则返回值，

9、则返回值 0； 若若S = T，则返回值，则返回值= 0； 若若S T，则返回值，则返回值 0。例如：例如：StrCompare( data , state ) 0144.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作 6） StrLength (S)StrLength (S) 初始条件：初始条件：串串 S 存在。存在。 操作结果：操作结果：返回返回 S 的元素个数，的元素个数， 称为串的长度。称为串的长度。154.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作7 7） Concat (&T, S1, S2)初始条件：初始条件：串串 S 1和和S

10、2存在。存在。操作结果：操作结果：用用T T返回由返回由S1S1和和S2S2联接而成的新串。联接而成的新串。例如：例如： Concat( T, man , kind ) 求得求得 T = mankind 164.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作8 8） SubString (&Sub, S, pos, len)初始条件：初始条件：串串 S 存在，存在，1posStrLength(S) 且且 0lenStrLength(S)pos+1。操作结果：操作结果：用用SubSub返回串返回串S S的第的第 pos pos 个字符起个字符起 长度为长度为lenlen的

11、子串。的子串。例如：例如： SubString( sub, commander , 4, 3)子串为子串为“串串”中的一个字符子序列中的一个字符子序列求得求得 sub = man ;SubString(sub, commander , 4, 7) sub = ? SubString(sub， student , 5, 0) = 184.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作9 9） Index (S, T, pos)初始条件：初始条件：串串S和和T存在，存在，T是非空串，是非空串， 1posStrLength(S)。操作结果：操作结果：若主串若主串 S S 中存

12、在和串中存在和串 T T 值相同的值相同的 子串子串, , 则返回它在主串则返回它在主串 S S 中第中第pospos 个字符个字符起起第一次出现的第一次出现的位置位置; ; 否则函数值为否则函数值为0 0。“子串在主串中的位置子串在主串中的位置”指子串中的第一个字符指子串中的第一个字符在主串中的位序。在主串中的位序。例如：假设例如：假设 S = abcaabcaaabc , T = bca Index(S, T, 1) = Index(S, T, 3) = Index(S, T, 8) = 2;6;0;204.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作1010）

13、Replace (&S, T, V)初始条件：初始条件：串串S, T和和 V 均已存在，均已存在， 且且 T 是非空串。是非空串。操作结果：操作结果：用用V V替换主串替换主串S S中出现的所有与中出现的所有与 （模式串）（模式串）T T相等的不重叠的子串。相等的不重叠的子串。214.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作1111） StrInsert (&S, pos, T)初始条件：初始条件：串串S和和T存在，存在， 1posStrLength(S)1。操作结果：操作结果：在串在串S S的第的第pospos个字符个字符之前之前插入串插入串T T。例如：例如：

14、S = chater ，T = rac ， 则执行则执行 StrInsert(S, 4, T) 之后得到之后得到 S = character 224.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作1212） StrDelete (&S, pos, len)初始条件：初始条件：串串S存在存在 1posStrLength(S)-len+1。操作结果：操作结果：从串从串S S中删除第中删除第pospos个字符个字符 起长度为起长度为lenlen的子串。的子串。 234.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作1313） ClearString (

15、&S)初始条件：初始条件：串串S存在。存在。操作结果：操作结果：将将S S清为空串。清为空串。244.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作 对于串的基本操作集可以有不同的定义方法，对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。语言的参考手册为准。 gets(str) 输入一个串；输入一个串； puts(str) 输出一个串；输出一个串； strcat(str1, str2) 串联接函数；串联接函数； strcpy(str1, str2, k) 串复制函数；串复制函

16、数； strcmp(str1, str2) 串比较函数；串比较函数； strlen(str) 求串长函数；求串长函数；例如例如：C语言函数库中提供下列串处理函数：语言函数库中提供下列串处理函数：254.1 4.1 串类型的定义串类型的定义6 6、串的基本操作、串的基本操作 串赋值串赋值StrAssignStrAssign、串复制、串复制StrcopyStrcopy、 串比较串比较StrCompareStrCompare、求串长、求串长StrLengthStrLength、 串联接串联接ConcatConcat以及求子串以及求子串SubStringSubString 等六种操作构成串类型的等六种

17、操作构成串类型的最小操作子集最小操作子集。在上述抽象数据类型定义的在上述抽象数据类型定义的13种操作中，种操作中，即：这些操作不可能利用其他串操作来实现，即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除反之，其他串操作（除串清除ClearString和和 串销毁串销毁DestroyString外）可在这个最小操作子外）可在这个最小操作子 集上实现。集上实现。Index (S, T, pos)Replace (&S, T, V)StrDelete (&S, pos, len)StrInsert (&S, pos, T)StrEmpty (S)264.1 4.1 串类型的定义串

18、类型的定义6 6、串的基本操作、串的基本操作 例如，可利用例如，可利用串比较串比较、求串长和求子串等操作实、求串长和求子串等操作实现定位函数现定位函数 Index( S, T, pos )。 StrCompare( ) S 串 T 串 T 串iposn-m+1算法的基本思想为：算法的基本思想为：SubString(S, i, StrLength(T), T int Index (String S, String T, int pos) / T为非空串。若主串为非空串。若主串S中第中第pos个字符之后存在与个字符之后存在与 T相等的子串，相等的子串， / 则返回第一个这样的子串在则返回第一个这样

19、的子串在S中的中的 位置，否则返回位置，否则返回0 if (pos 0) / if return 0; / S中不存在与中不存在与T相等的子串相等的子串 / Indexn = StrLength(S); m = StrLength(T); i = pos;while ( i = n-m+1) /1.循环循环 / whileSubString (sub, S, i, m); /2. 子串子串if (StrCompare(sub,T) != 0) +i ; /3. 比较比较else return i ;/S/S中从第中从第i i个字符之后存在与个字符之后存在与T T相等的子串相等的子串27又如串的

20、置换函数又如串的置换函数：Replace (&S, T, V) S 串 T 串 V 串 V 串pospos sub1news 串sub1= i+mposn-pos+1ii T 串isub2 sub2 V 串 剩余串剩余串 剩余串剩余串28void replace(String& S, String T, String V) /replacewhile ( pos = n-m+1 & i) 1.1.循环循环 i=Index(S, T, pos); /2./2.在在S S中定位子串中定位子串T T的位置的位置i i， if (i!=0) /定位成功定位成功 SubString(sub, S, po

21、s, i-pos); / 3. 取取S中保留的子串中保留的子串 Concat(news, news，sub); / 4. 连接连接 Concat(news, news, V); pos = i+m; /5./5.下一次定位的位置下一次定位的位置 /if/whileSubString(sub, S, pos, n-pos+1); / 剩余串剩余串Concat( S, news, sub );n=StrLength(S); m=StrLength(T); pos = 1;StrAssign(news, NullStr); i=1;29304.2 4.2 串表示和实现串表示和实现1 1、定长顺序存储

22、表示、定长顺序存储表示2 2、堆分配存储表示、堆分配存储表示3 3、块链存储表示、块链存储表示314.2 4.2 串的表示和实现串的表示和实现1 1、定长顺序存储表示、定长顺序存储表示n 静态分配静态分配 为每个串为每个串预先分配预先分配一个一个固定长度固定长度的存储区域。的存储区域。n 用定长数组描述用定长数组描述 #define MAXSTRLEN 255 #define MAXSTRLEN 255 /最大串长最大串长typedef unsigned char SStringMAXSTRLEN + 1 typedef unsigned char SStringMAXSTRLEN + 1 /

23、0/0号单元存放串的长度号单元存放串的长度324.2 4.2 串的表示和实现串的表示和实现1 1、定长顺序存储表示、定长顺序存储表示n实际串长可在所分配的固定长度区域内变动实际串长可在所分配的固定长度区域内变动以下标为以下标为0的数组分量存放串的实际长度；的数组分量存放串的实际长度；在串值后加入在串值后加入”0”表示结束，此时串长为隐含值。表示结束，此时串长为隐含值。334.2 4.2 串的表示和实现串的表示和实现1 1、定长顺序存储表示、定长顺序存储表示n 串的操作串的操作 （1 1）串的连接）串的连接 （2 2）求子串）求子串344.2 4.2 串的表示和实现串的表示和实现（1 1）串的连

24、接（见算法）串的连接（见算法4.24.2） Status Concat(SString &T, SString S1, SString S2) / 用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断, 则返回则返回TRUE，否则否则FALSE。 return uncut; / Concat T 1, , S10 = S1 1, , S10 ; T S10+1,.,S10+S20 =S2 1,.,S20 ; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断未截断 else if (S10 MAXSTR

25、SIZE) / 截断截断 else / 截断截断(仅取仅取S1)T 1,.,S10 = S1 1,.,S10 ;T S10+1,.,MAXSTRLEN = S2 1,.,MAXSTRLENS10 ;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; uncut = FALSE; 354.2 4.2 串的表示和实现串的表示和实现（2 2）求子串（见算法）求子串（见算法4.34.3） Status SubString(SString &Sub, SString S, int pos ,int len ) / 用用Sub返回串返回

26、串S的第的第pos个字符起长度为个字符起长度为len的子串。的子串。 / 其中，其中， 1posStrLength(S)1posStrLength(S)且且 0lenStrLength(S)-0lenStrLength(S)- pos+1 if（posS0|lenS0-pos+1） return ERROR; Sub1.len = Spos.pos+len-1; Sub 0 = len ; return OK; / SubStringSubString364.2 4.2 串的表示和实现串的表示和实现1 1、定长顺序存储表示、定长顺序存储表示n 操作特点操作特点 （1 1）实现串操作的原操作为）

27、实现串操作的原操作为“字符序列的复制字符序列的复制” （2 2）在操作中当出现串的长度超过）在操作中当出现串的长度超过MAXSTRLENMAXSTRLEN时，时，约定用截断法处理。约定用截断法处理。374.2 4.2 串的表示和实现串的表示和实现2 2、堆分配存储表示、堆分配存储表示n 动态分配动态分配 这种存储表示的特点是，仍以一组地址连续这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称间是在程序执行过程中动态分配而得。所以也称为为动态存储分配的顺序表动态存储分配的顺序表。在。

28、在C C语言中，利用语言中，利用mallocmalloc（）和（）和freefree（）等动态存储管理函数，来（）等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。根据实际需要动态分配和释放字符数组空间。384.2 4.2 串的表示和实现串的表示和实现2 2、堆分配存储表示、堆分配存储表示n 堆分配的存储表示堆分配的存储表示 typedef struct typedef struct char char * *ch; ch; / / 若是非空串，则按串实用长度分配存储区，否则若是非空串，则按串实用长度分配存储区，否则 ch ch 为为NULLNULL int length; / i

29、nt length; / 串长度串长度 HString; HString;394.2 4.2 串的表示和实现串的表示和实现2 2、堆分配存储表示、堆分配存储表示n基本操作基本操作串插入串插入 Status StrInsert(HString &S,int pos,HString T)串赋值串赋值 Status StrAssign(HString &S,char *chars)求串长求串长 int StrLength(HString S)串比较串比较 int StrCompare(HString S,HString T)串清空串清空 Status ClearString(HString &S)串

30、联接串联接 Status Concat(HString &S,HString S1,HString S2)求子串求子串 Status SubString(HString &Sub,HString S,int pos,int len)40算法算法4.4 串插入串插入Status StrInsert(HString &S,int pos,HString T)/在串在串S的第的第pos个位置前插入串个位置前插入串Tint i;if (posS.length+1) return ERROR;if (T.length)if (!(S.ch=(char*) realloc(S.ch,(S.length+T

31、.length)*sizeof(char)exit(OVERFLOW);for (i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;for (i=0; i=T.length-1;i+)S.chpos-1+i=T.chi;S.length+=T.length; return OK;串赋值串赋值Status StrAssign(HString &S,char *chars) /生成一个值等于生成一个值等于chars的串的串Sint i,j; char *c;for (i=0,c=chars;*c;+i,+c);if (!i) S.ch=NULL; S.len

32、gth=0;else if (!(S.ch=(char *)malloc(i * sizeof(char)exit(OVERFLOW);for (j=0;j=i-1;j+)S.chj=charsj;S.length=i;return OK; 41求串长求串长int StrLength(HString S)/求串的长度求串的长度return S.length;42串比较串比较 int StrCompare(HString S,HString T)/比较两个串，若相等返回比较两个串，若相等返回0int i;for (i=0;iS.length & iT.length; +i) if (S.chi

33、!= T.chi) return S.chi-T.chi; return S.length-T.length;43串清空串清空 Status ClearString(HString &S)/将将S清为空串清为空串if (S.ch) free(S.ch); S.ch=NULL;S.length=0;return OK;44串连接串连接 Status Concat(HString &S,HString S1,HString S2)/用用S返回由返回由S1和和S2联接而成的新串联接而成的新串 int j;if (!(S.ch = (char*)malloc(S1.length+S2.length)

34、*sizeof(char)exit(OVERFLOW);for (j=0;j=S1.length-1;j+) S.chj=S1.chj;S.length=S1.length+S2.length;for (j=0;j=S2.length-1;j+) S.chS1.length+j=S2.chj;return OK;45求子串求子串Status SubString(HString &Sub,HString S,int pos,int len)/用用Sub返回串返回串S的第的第pos个字符开始长度为个字符开始长度为len的子串的子串if (posS.length | lenS.length-pos+

35、1)return ERROR;if (!len) Sub.ch=NULL; Sub.length=0;else Sub.ch=(char *)malloc(len*sizeof(char);for (int j=0;j=len-1;j+)Sub.chj=S.chpos-1+j;Sub.length=len;return OK;46474.2 4.2 串的表示和实现串的表示和实现3 3、串的块链存储表示、串的块链存储表示n 为什么要采用链式存储为什么要采用链式存储 顺序串上的顺序串上的插入插入和和删除删除操作操作不方便不方便，需要，需要移移动大量动大量的字符。因此，可用单链表方式来存储串的字符。

36、因此，可用单链表方式来存储串值，值，串的这种链式存储结构简称为链串串的这种链式存储结构简称为链串。484.2 4.2 串的表示和实现串的表示和实现3 3、串的块链存储表示、串的块链存储表示n 串的链式存储表示串的链式存储表示typedef struct nodetypedef struct node char data; char data; struct node struct node * *next;next;lstringlstring特点：特点：这种结构这种结构便于便于进行进行插入插入和和删除运算删除运算，但，但存储空间利用率太低存储空间利用率太低。 （P78 P78 图图4.24.

37、2（b b） 494.2 4.2 串的表示和实现串的表示和实现3 3、串的块链存储表示、串的块链存储表示n 串的块链存储表示串的块链存储表示 为了提高为了提高存储密度存储密度，可使每个结点存放多个，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义字符。通常将结点数据域存放的字符个数定义为为结点的大小结点的大小，显然，当结点大小大于，显然，当结点大小大于 1 1时，时，串的长度不一定正好是结点的整数倍，因此要串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点用特殊字符来填充最后一个结点，以表示串的，以表示串的终结。（终结。（P78 P78 图图4.24.2（a a）

38、 存储密度存储密度= =串值所占的存储位串值所占的存储位 实际分配的存储位实际分配的存储位504.2 4.2 串的表示和实现串的表示和实现3 3、串的块链存储表示、串的块链存储表示n 串的块链存储表示串的块链存储表示 对于结点大小不为对于结点大小不为1 1的链串，其类型定义只的链串，其类型定义只需对上述的结点类型做简单的修改即可。需对上述的结点类型做简单的修改即可。 #define nodesize 80#define nodesize 80 typedef struct node typedef struct node char datanodesize; char datanodesize

39、; struct node struct node * *next;next; LString; LString; 514.3 4.3 串的模式匹配算法串的模式匹配算法1 1、模式匹配、模式匹配2 2、模式匹配算法、模式匹配算法524.3 4.3 串的模式匹配算法串的模式匹配算法（1 1）BFBF算法的基本思想算法的基本思想534.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a bi=3，j=3失败；失败；i回溯到回溯到2，j回溯到回溯到1ijijija b c a c 544.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b

40、a b c a b c a c b a bi=3，j=3失败；失败；i回溯到回溯到2，j回溯到回溯到1jia b c a c 554.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a bi=2，j=1失败失败i回溯到回溯到3，j回溯到回溯到1ija b c a c 564.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a bi=2，j=1失败失败i回溯到回溯到3，j回溯到回溯到1ija b c a c 574.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b

41、c a c b a ba b c a c i=7，j=5失败失败i回溯到回溯到4，j回溯到回溯到1ijijijijij584.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a ba b c a c i=7，j=5失败失败i回溯到回溯到4，j回溯到回溯到1ij594.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a ba b c a c i=4，j=1失败失败i回溯到回溯到5，j回溯到回溯到1ij604.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a

42、c b a ba b c a c i=4，j=1失败失败i回溯到回溯到5，j回溯到回溯到1ij614.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a ba b c a c i=5，j=1失败失败i回溯到回溯到6，j回溯到回溯到1ij624.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a ba b c a c i=5，j=1失败失败i回溯到回溯到6，j回溯到回溯到1ij634.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）a b a b c a b c a c b a ba b c

43、 a c ijijijijij644.3 4.3 串的模式匹配算法串的模式匹配算法（3 3）654.3 4.3 串的模式匹配算法串的模式匹配算法（4 4）例如：例如：s=aaaaabcd t=bcds=aaaaabcd t=bcd“11111()(1)(1)12n mn miiinmpimimnm 因此最好情况下的时间复杂度是因此最好情况下的时间复杂度是O(n+m)O(n+m)。664.3 4.3 串的模式匹配算法串的模式匹配算法（4 4）例如：例如：s=aaaaab t= aaabs=aaaaab t= aaab“11111(2)()()12in mn miimn mpi mi mn m 6

44、74.3 4.3 串的模式匹配算法串的模式匹配算法思考思考：为什么为什么BFBF算法时间性能低？算法时间性能低？ 684.3 4.3 串的模式匹配算法串的模式匹配算法（1 1）KMPKMP算法的基本思想算法的基本思想694.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配过程算法的匹配过程i=3，j=3失败；失败； s2=t2;t1t2t1s2a b a b c a b c a c b a bija b c a c a b a b c a b c a c b a ba b c a c 704.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹

45、配过程算法的匹配过程i=3，j=3失败；失败； s2=t2;t1t2t1s2a b a b c a b c a c b a bija b c a c a b a b c a b c a c b a ba b c a c 714.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配过程算法的匹配过程a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s4=t2;t1t2t1s4a b a b c a b c a c b a ba b c a c 724.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配

46、过程算法的匹配过程a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 734.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配过程算法的匹配过程a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 匹配成功匹配成功744.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算

47、法的匹配过程算法的匹配过程754.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配过程算法的匹配过程（1）设模式滑动到第）设模式滑动到第k个字符，则个字符，则 S S=a b a b c a b c a c b a bT= =a b c a cikjS=a b a b c a b c a c b a bT= =a b c a cik764.3 4.3 串的模式匹配算法串的模式匹配算法（2 2）KMPKMP算法的匹配过程算法的匹配过程请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：两式联立可得：两式联立可得：（2）则）则Tj-(k-1) Tj-1 SS=a b a b c a b c a c b a bT= =a b c a cik