东北师范大学《离散数学》课件-第十一讲.pdfVIP

离散数学 第11讲 字母表与串 Alphabet and String 字母表与串  字母表 （alphabet ）是指一个有限的非空符 号集 ， 中元素称为字母。   为所有由 中元素生成的有限长度序列全  体， 中元素称为  上的词 （word ）或串 （string ） （在不引起混淆时，也可忽略序 列各项间的“,”），即串是有限长度的符号序 列。   中的空序列称作空串 （empty string）， 习惯上使用 或 表示，用表示集合{} 。 2 字母表与串  串w 所含字母个数 （即序列的项数）称作w 的长 度(length) ，记作|w| 。  可以这样来理解：字母表是有限的符号集，而串 是有限长度的符号序列。  假设 w =s s s …s 和 w =t t t …t 都是字母表  1 1 2 3 n 2 1 2 3 m 上 的串 ，则 w1 和 w2 的连接 定义 为 s s s …s t t t …t ，记作w ◦w 或w w 。◦称作 1 2 3 n 1 2 3 m 1 2 1 2 上的连接运算。  容易看出串在连接运算下形成的代数结构：   假设 是一个字母表，则( , ◦) 构成一个半群 3 字母表与串 例  常用的字母表有：   = {0, 1} ，二进制字母表；   = {a, b, ..., z} ，所有小写字母的集合；  所有ASCII字符的集合，或者所有可打印的ASCII字 符的集合。 例  01101是二进制字母表 ={0, 1} 上的一个串， 长度为5  111是这个字母表上的另一个串，长度为3  空串 的长度为0 4 字母表与串 假设 w 是字母表  上的串，则可以定 义w 的n 次幂w n 为  (1) w 0 =，  (2) w n = w n1 ◦w ，n1。 例 3 2  a =aaa ，(ab) a=ababa n n  {0 1 | n1}={01,0011,000111, } 5 字母表与串  假设x, y , z 是字母表 上的串，且x = yz 。  称y 是x 的前缀 （prefix）  如果z ，则称y 是x 的真前缀 （proper prefix）  称z 是x 的后缀 （suffix）  如果y ，则称z 是x 的真后缀 （proper suffix）  假设x , y 是字母表 上的串，且存在字母表 上 的串 z, w 使得 x = zyw ，则称 y 是 x 的子串 （substring）  简言之，x 的子串就是由 x 删除某个前缀后再删去 某个后缀得到的结果。 6 字母表与串 例  串abcde的 前缀是, a, ab, a