串的定义及基本运算

1、n本章内容本章内容4.1 串的定义及基本运算串的定义及基本运算4.2 串的表示和实现串的表示和实现4.3 串的模式匹配串的模式匹配4.3.1 基本的模式匹配算法基本的模式匹配算法4.3.2 kmp模式匹配算法模式匹配算法4.4 串操作应用举例串操作应用举例4.1 串的定义及基本运算串的定义及基本运算n串的定义串的定义串串(string)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。一般记作：一般记作：s=“a1a2a3an”，其中：其中：s：串名串名；“a1a2a3an”：串值，双引号括起来的字符序列；串值，双引号括起来的字符序列； ai(1in)可以是字母、数字或其它字符；

2、可以是字母、数字或其它字符；n串的长度串的长度：串中所包含的字符个数；：串中所包含的字符个数；n长度为零的串称为空串长度为零的串称为空串(empty string)，它不包含任它不包含任何字符。何字符。n空白串空白串: :通常将仅由一个或多个空格组成的串称为空白串通常将仅由一个或多个空格组成的串称为空白串(blank string)。 注意：空串和空白串的不同。注意：空串和空白串的不同。4.1 串的定义及基本运算串的定义及基本运算n串的子串：串的子串：串中任意个连续字符组成的子序列称为该串串中任意个连续字符组成的子序列称为该串的的子串子串(substring)，包含子串的串相应地称为包含子串的

3、串相应地称为主串主串。通常将子串在主串中首次出现时的该子串的首字符对应通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位的主串中的序号，定义为子串在主串中的序号（或位置）。置）。n例如：例如：设设a a和和b b分别为分别为a=“this is a string” a=“this is a string” b=“is”b=“is”则则b b是是a a的子串，的子串，a a为主串。为主串。b b在在a a中出现了两次，中出现了两次，其中首次出现所对应的主串位置是其中首次出现所对应的主串位置是3 3。因此，称。因此，称b b在在a a中的位置为中的位置为

4、3 3。特别地，空串是任意串的子串，任意串是其自身的子串。特别地，空串是任意串的子串，任意串是其自身的子串。4.1 串的定义及基本运算串的定义及基本运算n串的基本运算串的基本运算n串赋值串赋值: strassign(&s, char *t)n串比较串比较: int strcompare(s, t)n求串长求串长: int strlength(s) n串联接串联接: char *strcat(char *to, char *from) n求子串求子串: substring(&sub, s, pos, len)n串复制串复制 : char *strcpy(char *to,char

5、 *from) n子串定位子串定位: int index(sub,s) 4.2 串的表示和实现串的表示和实现n串的定长顺序存储串的定长顺序存储maxstrlen-1.01使用数组存储串使用数组存储串#define maxstrlen 256typedef char sstringmaxstrlen;sstring s; /s可容纳可容纳255个字符个字符 串作为高级语言支持的数据类型，串作为高级语言支持的数据类型，对于串长度对于串长度(或串的结尾表示或串的结尾表示)，会有不，会有不同的方式，对于超过串存储空间的部分同的方式，对于超过串存储空间的部分会截断存储。会截断存储。可以在串定义中加入串长

6、表示：可以在串定义中加入串长表示：typedef struct char chmaxstrlen; int length;sstring;4.2 串的表示和实现串的表示和实现n顺序串的操作实现顺序串的操作实现(1) 串连接串连接concat(&t,s1,s2) s1.length+s2.length= maxstrlen s1.lengthmaxstrlens2中被截去的部分中被截去的部分 s1.length = maxstrlentts1.lengths1s2.lengths2ts2串被全部截去串被全部截去4.2 串的表示和实现串的表示和实现n顺序串的操作实现顺序串的操作实现(2)

7、求子串求子串substring(&sub,s,pos,len) status substring(sstring &sub,sstring s,int pos,int len) /求串求串s从第从第pos个字符起长度为个字符起长度为len的子串的子串sub if (pos s.length | lens.length-pos+1) return error; sub.ch0.len-1 = s.chpos-1.pos+len; sub.length = len;n顺序串存储存在的问题？顺序串存储存在的问题？4.2 串的表示和实现串的表示和实现n串的堆分配存储串的堆分配存储在程序

8、执行过程中从内存空闲区在程序执行过程中从内存空闲区(堆堆)中动态申请满中动态申请满足串长的存储空间，串在其中仍是顺序存储的，称为足串长的存储空间，串在其中仍是顺序存储的，称为堆堆结构结构。也称为也称为动态存储分配的顺序表动态存储分配的顺序表。n串的堆分配存储定义串的堆分配存储定义 typedef char *string; /c c中的串库相当于此中的串库相当于此类型定义类型定义 /-串的堆分配存储表示串的堆分配存储表示- typedef struct char *ch; int length; hsring;4.2 串的表示和实现串的表示和实现n基本操作的实现基本操作的实现(1)串赋值串赋值

9、status strassign(hstring &t,char *chars) /生成一个其值等于串常量生成一个其值等于串常量charschars的串的串t t if(t.ch) free(t.ch); for(i = 0,c = chars;c; +i,+c); /求求chars长度长度 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;4.2

10、 串的表示和实现串的表示和实现(2)串联接串联接 status concat(hstring &t, hstring s1, hstring s2) /将串将串s1s1和和s2s2联接成新串联接成新串t t if (!(t.ch) = (char*)malloc(s1.length+ s2.length)*sizeof(char) exit(overflow); t.ch0.s1.length-1 = s1.ch0.s1.length-1; t.chs1.length.t.length-1 = s2.ch0.s2.length-1; t.length = s1.length + s2.

11、length; return ok;4.2 串的表示和实现串的表示和实现(3)求子串求子串 status substr(hstring &sub,hstring s,int pos,int len) if (poss.length | lens.length-pos+1) return error; if (sub.ch) free(sub.ch); if (!len) sub.ch = null; sub.length = 0; else sub.ch = (char *)malloc(len*sizeof(char); sub.ch0.len - 1 = spos-1.pos +

12、len-2; s.length = len; 请自学有关堆分配串的其他操作的实现请自学有关堆分配串的其他操作的实现!4.2 串的表示和实现串的表示和实现n串的链式存储串的链式存储s结点大小为结点大小为1的单链表的单链表a b c m 存储密度：存储密度： 串值所占的存储空间串值所占的存储空间 实际分配的存储空间实际分配的存储空间s结点大小为结点大小为4的单链表的单链表 dcba hgfe#m4.3 串的模式匹配串的模式匹配子串定位运算又称为子串定位运算又称为模式匹配模式匹配(pattern matching)或或串匹配串匹配(string matching)。在串匹配中，一般将主串称为在串匹配

13、中，一般将主串称为目标串目标串，子串，子串称为称为模式串模式串。若子串在主串中出现，则称若子串在主串中出现，则称匹配成功匹配成功，子串，子串出现的位置称为出现的位置称为有效位移有效位移, ,否则称否则称匹配不成功匹配不成功。模式匹配在文章的关键字查找中被广泛使用。模式匹配在文章的关键字查找中被广泛使用。4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第一趟第一趟 (初始初始i=1)i=1j=

14、1？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第一趟第一趟 (初始初始i=1)i=2j=2？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第一趟第一趟 (初始初始i=1)i=3j=

15、3？不同4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第二趟第二趟 (初始初始i=2)i=2j=1？不同4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第三趟第三趟 (初始初始i=3)i

16、=3j=1？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第三趟第三趟 (初始初始i=3)i=4j=2？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第三趟第三趟 (初始初始i=3)i

17、=5j=3？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第三趟第三趟 (初始初始i=3)i=6j=4？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第三趟第三趟 (初始初始i=3)i

18、=7j=5？不同4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第四趟第四趟 (初始初始i=4)i=4j=1？不同4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第五趟第五趟 (初始初始i

19、=5)i=5j=1？不同4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第六趟第六趟 (初始初始i=6)i=6j=1？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第六趟第六趟 (初始初

20、始i=6)i=7j=2？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第六趟第六趟 (初始初始i=6)i=8j=3？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第六趟第六趟 (初始初

21、始i=6)i=9j=4？4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法例：例：主串主串s：ababcabcacbab 子串子串t：abcaca b a b c a b c a c b a b主串：主串：a b c a c子串：子串：第六趟第六趟 (初始初始i=6)i=10j=5？模式串结束4.3 串的模式匹配串的模式匹配问题： 当主串中的第当主串中的第i个字符与模式串中的第个字符与模式串中的第j个不相个不相等时，等时， 如何处理？如何处理？a b a b c a b c a c b a b主串：主串：a b c a c子串：子串：i=7j=5？不同

22、不同主串的字符下标主串的字符下标i i回退到位置回退到位置i-j+2i-j+2，然后从模式串的第然后从模式串的第一个字符一个字符( (j=1)j=1)开始，继续匹配过程开始，继续匹配过程。i的回退称为的回退称为回溯回溯。 匹配成功的标志？匹配成功的标志？jt.length4.3 串的模式匹配串的模式匹配n模式匹配算法模式匹配算法n朴素的串匹配算法朴素的串匹配算法int index(sstring s,sstring t,int pos) /返回子串返回子串t在主串在主串s中从第中从第pos个字符开始的位置个字符开始的位置/要求要求t非空，非空，1pos strlength(s) i = pos

23、; j = 1; while (i = strlength(s) & j strlength(t) ) return (istrlength(t); return 0; / index算法时间复杂度算法时间复杂度?o(n*m)，其中，其中n、m分别为主串和子串长度分别为主串和子串长度4.3 串的模式匹配串的模式匹配n改进的串匹配算法改进的串匹配算法kmp算法算法问题的提出：问题的提出：当主串的第当主串的第i个字符与子串的第个字符与子串的第j个字符失配时，子串的个字符失配时，子串的前前(j-1)个字符与主串的第个字符与主串的第i个字符前的个字符前的(j-1)个字符已经个字符已经比较过。若

24、有主串的第比较过。若有主串的第i个字符前的个字符前的(k-1)个字符与子串个字符与子串的前的前(k-1)个字符匹配，则只需主串的第个字符匹配，则只需主串的第i个字符与子串个字符与子串的第的第k个字符开始向后比较即可，个字符开始向后比较即可，i不必回溯。不必回溯。a b a b c a b c a c b a b主串：主串：a b c a c子串：子串：i=7j=5？不同不同4.3 串的模式匹配串的模式匹配n改进的串匹配算法改进的串匹配算法kmp算法算法问题的提出：问题的提出：当主串的第当主串的第i个字符与子串的第个字符与子串的第j个字符失配时，子串的个字符失配时，子串的前前(j-1)个字符与主

25、串的第个字符与主串的第i个字符前的个字符前的(j-1)个字符已经个字符已经比较过。若有主串的第比较过。若有主串的第i个字符前的个字符前的(k-1)个字符与子串个字符与子串的前的前(k-1)个字符匹配，则只需主串的第个字符匹配，则只需主串的第i个字符与子串个字符与子串的第的第k个字符开始向后比较即可，个字符开始向后比较即可，i不必回溯。不必回溯。 k的值只与子串的组成有关，而与主串无关。的值只与子串的组成有关，而与主串无关。主串：主串： a b c d a b c d e 子串：子串：a b c d a b c d f准确地说，准确地说，k值与值与j当前位置之前的子串的结构相关，当前位置之前的子

26、串的结构相关，每一个每一个j位置对应一个位置对应一个k值，用值，用nextj存储。存储。4.3 串的模式匹配串的模式匹配n改进的串匹配算法改进的串匹配算法kmp算法算法nextj 的定义：的定义：nextj =maxk|1kj 且且p1.pk-1=pj-k+1.pj-1不重叠，但允许交差。不重叠，但允许交差。0 当当 j=1,它前面有它前面有0个字符与它的前个字符与它的前0 个字符匹个字符匹 配。表示与子串第一次比较就失败，应使配。表示与子串第一次比较就失败，应使i指向指向下一字符再与子串第一字符比较下一字符再与子串第一字符比较(i+;j+)。1 其他情况其他情况(j=2或或j前面没有匹配部分

27、前面没有匹配部分)例：例：j1 2 3 4 5 6 7 8模式串模式串a b a a b c a cnextj213221104.3 串的模式匹配串的模式匹配n改进的串匹配算法改进的串匹配算法kmp算法算法int index (sstring s,sstring t,int pos) /返回子串返回子串t在主串在主串s中从第中从第pos个字符开始的位置个字符开始的位置/要求要求t非空，非空，1pos strlength(s) i=pos; j=1; while(i=strlength(s) & j strlength(t) return (i-strlength(t); return 0; / index_kmpj=0 | j=nextj4.3 串的模式匹配串的模式匹配n改进的串匹配算法改进的串匹配算法kmp算法算法求模式串求模式串p p的的nextj 的算法：的算法：已知已知next1=0,nextj=k;如何由如何由nextj求得求得nextj+1?若若pj = pnextj，则，则nextj+1 = k+1(即即nextj+1 = nextj+1)；若若pjpn