数据与算法课程讲义（吴及）基础数据结构5-串与串匹配.pdfVIP

2012-2013秋季学期数据与算法课程讲义 基础数据结构 吴 及 wuji_ee@tsinghua.edu.cn 清华大学电子工程系 2012年10月 内容提要  二元关系与抽象数据类型  线性表 栈与队列  串 树与二叉树  图 数据与算法 2 吴及 电子工程系 串的概念  串： = 01 ⋯ ，  串是有限长度的字符序列  串是限定数据元素为字符的线性表  一个串的长度指的是串中所包含的字符个数 当 = 0 时，称为空串，记为 =  值得注意：  值为空格的字符串 空串： “” ≠  长度为1的字符串 单个字符：“” ≠ ‘′ (C/C++) 数据与算法 3 吴及 电子工程系 串的概念  字符在串中的序号称为该字符在串中的位置 = 01 ⋯ ， ≥ 0  两个串相等当且仅当  两个串的长度相等， 每个对应位置的字符也相同。 数据与算法 4 吴及 电子工程系 子串与主串  串中任意多个连续的字符组成的子序列称为该串的子串  包含该子串的串称为子串的主串  子串在主串中的位置指的是该子串的第一个字符在主串中的 位置  串的操作经常以子串为单位进行，这是与线性表的区别 数据与算法 5 吴及 电子工程系 串的概念  串的例子 = c = = =  长度，子串，位置  的长度为4 ，的长度为9 ，的长度为13 ，的长度为14 ； ≠  是的子串 ⊂ ， 也是的子串 ⊂ ；  是的子串 ⊂ ， 也是的子串 ⊂ ；  在和中的位置都是0 ；  在的位置为4 ， 在中的位置为5 ； 数据与算法 6 吴及 电子工程系