Schoolof Co buten Seicuac aud technology Page593324-2 。给出关于q的函数π[q的规模的严格上界,并加以举例说明 解:理解题意。 本题求解严格上界的对象是π[q的规模,不是π[q内元素值的上界。 πq]={πq,π(1q],r(2)[q],…,mr(Oq]},本身是一个集合,集合中的元 素由前缀函数π迭代生成。 当字符串中各字符均相同时,eg.aam[3]={2,1,0}, π'[q的规模上界为q,π[q内元素值的上界为q-1 20221
Page593 32.4-2 2021/2/11 17 。给出关于q的函数𝝅 ∗ [𝒒]的规模的严格上界，并加以举例说明。 解：理解题意。 本题求解严格上界的对象是𝝅 ∗ [𝒒]的规模，不是𝝅 ∗ [𝒒]内元素值的上界。 • 𝝅 ∗ [𝒒] = {𝝅 𝒒 , 𝝅 (𝟏) [𝒒] , 𝝅 (𝟐) [𝒒] ,…, 𝝅 (𝒕) [𝒒] }，本身是一个集合，集合中的元 素由前缀函数𝜋迭代生成。 • 当字符串中各字符均相同时,eg: aaa π ∗ [3] = {2, 1, 0}， 𝜋 ∗ [𝑞]的规模上界为q, 𝜋 ∗ [𝑞]内元素值的上界为q-1
Schoolof Co buten Seicuac aud technology Page593324-7 。写出一个线性时间的算法,以确定文本T是否是另一个字符串T的循环旋转。 eg: ABC BCA CAB互为循环旋转。 解:对于任意文本串T:C1C2C3…Cn-1Cm,其循环旋转依次有 C1 C3. Cn-1 Crcc Cnc,C2C3 C1C2C3. Cn_1Cn 任意文本串T的所有循环旋转一定存在于TT字符串中。 将T1与T2是否互为循环问题转换为使用KMP算法在T1T1文本串中寻找模式串 12 20221 18
Page593 32.4-7 2021/2/11 18 。写出一个线性时间的算法，以确定文本T是否是另一个字符串𝑻 ·的循环旋转。 eg: ABC BCA CAB互为循环旋转。 解：对于任意文本串T：𝐶1𝐶2𝐶3…𝐶𝑛−1𝐶𝑛，其循环旋转依次有 𝐶2𝐶3…𝐶𝑛−1𝐶𝑛𝐶1 𝐶3…𝐶𝑛−1𝐶𝑛𝐶1𝐶2 . . . 𝐶𝑛𝐶1𝐶2𝐶3…𝐶𝑛−1 𝐶1𝐶2𝐶3…𝐶𝑛−1𝐶𝑛 • 任意文本串T的所有循环旋转一定存在于TT字符串中。 • 将T1与T2是否互为循环问题转换为使用KMP算法在T1T1文本串中寻找模式串 T2
Schoolof Computer Science and 7ccheologg 1958 算法基础第二次习题课 助教:张帆 NCAA Network Computing and Advanced Algorithm Laboratory 19
算法基础第二次习题课 助教：张帆 19
Schoolof Co buten Seicuac aud technology 主讲部分 |Page12493-5; Page231155-2 Page24416.2-3 Page535302-2 Page18713.4-2 Page187134-3 Page587323-1323-2 20221
主讲部分 2021/2/11 20 • Page124 9.3-5; • Page231 15.5-2 • Page244 16.2-3 • Page535 30.2-2 • Page187 13.4-2 • Page187 13.4-3 • Page587 32.3-1 32.3-2
Schoolof Co buten Seicuac aud technology Page12493-5 解: 使用黑盒程序找到中位数,根据该中位数 SELECT(A,p,r,1 对数组进行分区。如果小于原始数组长度 if p 的一半,则在前半部分递归,如果i是数组 return Alpl 长度的一半,则返回来自中位数查找黑框 X= MEDIAN(A, p, r) 的元素。最后,如果i超过数组长度的一半 q= PARTITIONG 则减去数组长度的一半,然后递归到数组 k=q-p+l 的后半部分。 ifi==k return A q lse ifi<k return SELECT(A, p, q-1, 1) else return SELECT(A, q+l,r,1-k) 20221
Page124 9.3-5 2021/2/11 21 • 解： • 使用黑盒程序找到中位数，根据该中位数 对数组进行分区。 如果i小于原始数组长度 的一半，则在前半部分递归，如果i是数组 长度的一半，则返回来自中位数查找黑框 的元素。 最后，如果i超过数组长度的一半， 则减去数组长度的一半，然后递归到数组 的后半部分。 SELECT'(A, p, r, i) if p == r return A[p] x = MEDIAN(A, p, r) q = PARTITION(x) k = q - p + 1 if i == k return A[q] else if i < k return SELECT'(A, p, q - 1, i) else return SELECT'(A, q + 1, r, i - k)