刘勇4_1串

nullnull4.1 串及其运算 4.2 串的存储表示 4.3 串的模式匹配算法 穷举算法、KMP算法、改进的KMP算法； next数组、改进next数组 4.1 串及其运算串是由零个或多个字符组成的有限序列，一般记为 s=“a1a2…an”(n0) 其中，s是串名，用单引号（也可以是用双引号括起来的） 括起来的字符序列是串的值。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。4.1 串及其运算子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 位置：字符在序列中的序号。子串在主串中的位置则以子 串的第一个字符在主串中的位置来表示。 相等：两个串的长度相等，并且对应位置的字符都相等。注意区分空串与空格串的区别。null 串的逻辑结构和线性表的区别: 1. 串的数据对象约束为字符集。 2. 线性表的基本操作大多以“单个元素”为操作对象，而 串的基本操作通常以“串的整体”作为操作对象。 对于串可以定义以下运算： 1. 置串为一个空串； 2. 判断一个串是否为空串 3. 求一个串的长度； 4. 将两个串拼接在一起构成一个新串； 5. 在一个串中，求从串的第i个字符开始连续j个字符所构成的子串； 6. 如果串S2是S1的子串，则可求串S2在串S1中第一次出现的位置。 7、去掉首尾空格 8、全部大写、全部小写 9、分割串，得到串数组4.2串的存储表示1. 定长顺序表示 4.2串的存储表示算法4.1 求顺序表示的串的子串算法4.1 求顺序表示的串的子串其它操作其它操作2. 变长顺序表示2. 变长顺序表示3. 串的块链存储表示 3. 串的块链存储表示4.3 串的模式匹配算法模式匹配：子串（又称模式串）在主串中的定位操作。4.3 串的模式匹配算法定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 3 朴素算法--------穷举的模式匹配过程朴素算法--------穷举的模式匹配过程 朴素的模式匹配算法 朴素的模式匹配算法KMP算法KMP算法 由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的。简称KMP算法。 提高匹配效率 i指针不回溯 利用已匹配的信息定位j指针nullnext数组直观算法(下标从1开始)： (1) next[1] = 0 (2) next[j] = k+1的情况为：T[1..k]=T[j-k....j-1]迭代算法(下标从1开始)： (1) next[1] = 0,next[2] = 1 (2) j从3开始：k=next[j-1] 如T[next[j-1]] == T[next[k]] 则next[j]=k+1, 否则next[j] = 1null求next数组的算法null已知next数组后的匹配算法null改进的KMP算法：改进next数组已知next数组，求nextVal数组 (1) nextVal[1,2] = next[1,2] (2) j从3开始: k = next[j] 如 T[j] == T[k] ，则nextVal[j] = next[k] 否则nextVal[j] = next[j]