串的定义及基本运算

1、本章内容 4.1 串的定义及基本运算 4.2 串的表示和实现 4.3 串的模式匹配 4.3.1 基本的模式匹配算法 4.3.2 kmp模式匹配算法 4.4 串操作应用举例,4.1 串的定义及基本运算,串的定义 串(string)是零个或多个字符组成的有限序列。 一般记作：s=“a1a2a3an”，其中： s：串名； “a1a2a3an”：串值，双引号括起来的字符序列； ai(1in)可以是字母、数字或其它字符； 串的长度：串中所包含的字符个数； 长度为零的串称为空串(empty string)，它不包含任何字符。 空白串:通常将仅由一个或多个空格组成的串称为空白串(blank string)。

2、 注意：空串和空白串的不同,4.1 串的定义及基本运算,串的子串：串中任意个连续字符组成的子序列称为该串的子串(substring)，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。 例如：设a和b分别为a=“this is a string” b=“is” 则b是a的子串，a为主串。b在a中出现了两次，其中首次出现所对应的主串位置是3。因此，称b在a中的位置为3。 特别地，空串是任意串的子串，任意串是其自身的子串,4.1 串的定义及基本运算,串的基本运算 串赋值: strassign( sstring s; /s

3、可容纳255个字符 串作为高级语言支持的数据类型，对于串长度(或串的结尾表示)，会有不同的方式，对于超过串存储空间的部分会截断存储。 可以在串定义中加入串长表示： typedef struct char chmaxstrlen; int length; sstring,4.2 串的表示和实现,顺序串的操作实现 (1) 串连接concat( /c中的串库相当于此类型定义 /-串的堆分配存储表示- typedef struct char *ch; int length; hsring,4.2 串的表示和实现,基本操作的实现 (1)串赋值 status strassign(hstring,4.2 串

4、的表示和实现,2)串联接 status concat(hstring,4.2 串的表示和实现,3)求子串 status substr(hstring,请自学有关堆分配串的其他操作的实现,4.2 串的表示和实现,串的链式存储,存储密度： 串值所占的存储空间 实际分配的存储空间,4.3 串的模式匹配,子串定位运算又称为模式匹配(pattern matching)或串匹配(string matching)。 在串匹配中，一般将主串称为目标串，子串称为模式串。 若子串在主串中出现，则称匹配成功，子串出现的位置称为有效位移,否则称匹配不成功。 模式匹配在文章的关键字查找中被广泛使用,4.3 串的模式匹配

5、,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第一趟 (初始i=1,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第一趟 (初始i=1,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第一趟 (初始i=1,不同,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第二趟 (初始i=2,不同,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s

6、：ababcabcacbab 子串t：abcac,第三趟 (初始i=3,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第三趟 (初始i=3,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第三趟 (初始i=3,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第三趟 (初始i=3,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,第三趟

7、 (初始i=3,不同,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第四趟 (初始i=4,不同,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第五趟 (初始i=5,不同,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第六趟 (初始i=6,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第六趟 (初始i=6

8、,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第六趟 (初始i=6,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第六趟 (初始i=6,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 例：主串s：ababcabcacbab 子串t：abcac,子串,第六趟 (初始i=6,模式串结束,4.3 串的模式匹配,问题： 当主串中的第i个字符与模式串中的第j个不相等时， 如何处理,主串的字符下标i回退到位置i-j+2，然后从模式串的第一个字符(j=1

9、)开始，继续匹配过程。 i的回退称为回溯。 匹配成功的标志？ jt.length,4.3 串的模式匹配,模式匹配算法 朴素的串匹配算法 int index(sstring s,sstring t,int pos) /返回子串t在主串s中从第pos个字符开始的位置 /要求t非空，1pos strlength(s) i = pos; j = 1; while (i strlength(t) ) return (istrlength(t); return 0; / index,算法时间复杂度,o(n*m)，其中n、m分别为主串和子串长度,4.3 串的模式匹配,改进的串匹配算法kmp算法 问题的提出：

10、 当主串的第i个字符与子串的第j个字符失配时，子串的前(j-1)个字符与主串的第i个字符前的(j-1)个字符已经比较过。若有主串的第i个字符前的(k-1)个字符与子串的前(k-1)个字符匹配，则只需主串的第i个字符与子串的第k个字符开始向后比较即可，i不必回溯,4.3 串的模式匹配,改进的串匹配算法kmp算法 问题的提出： 当主串的第i个字符与子串的第j个字符失配时，子串的前(j-1)个字符与主串的第i个字符前的(j-1)个字符已经比较过。若有主串的第i个字符前的(k-1)个字符与子串的前(k-1)个字符匹配，则只需主串的第i个字符与子串的第k个字符开始向后比较即可，i不必回溯。 k的值只与子

11、串的组成有关，而与主串无关,准确地说，k值与j当前位置之前的子串的结构相关，每一个j位置对应一个k值，用nextj存储,4.3 串的模式匹配,改进的串匹配算法kmp算法 nextj 的定义,例,2,1,3,2,2,1,1,0,4.3 串的模式匹配,改进的串匹配算法kmp算法 int index (sstring s,sstring t,int pos) /返回子串t在主串s中从第pos个字符开始的位置 /要求t非空，1pos strlength(s) i=pos; j=1; while(i strlength(t) return (i-strlength(t); return 0; / ind

12、ex,_kmp,j=0 ,4.3 串的模式匹配,改进的串匹配算法kmp算法 求模式串p的nextj 的算法,已知next1=0,nextj=k;如何由nextj求得nextj+1? 若pj = pnextj，则nextj+1 = k+1(即nextj+1 = nextj+1)； 若pjpnextj，则令pj和pnextnextj比较； 若相等，则nextj+1 = nextnextj+1； 若不等，则沿失败链继续查找，直到某个pnext.nextj. = pj，或next.nextj.=0，这时都置 nextj+1 = next.nextj.+1,若sipj，且模式中 p1p2 .pk-1 pj-k+1pj-k+2 .pj-1 则可令si与pk进行比较,4.3 串的模式匹配,改进的串匹配算法kmp算法 求nextj 的算法： (1)由定义，next1=0 (2)设nextj=k，则1kj，满足： p1pk-1=pj-k+1pj-1 若pk = pj，则nextj+1= nextj+1; 若pk pj，此时看作模式串作为子串与自身在第k位失配，应从nextk位开始与j位比较，若pnextk pj，即重复直至相等或初始条件next1=0；若pnextk = pj ，则nextj+1=nextk+1,2,1,4.3 串的模式匹配,改进的串匹配算法kmp算法 求