当前课程知识点：Data Structures and Algorithm Design Part II >  11.String II >  E2.Bm_GS.constructing_gs[] >  11E2

返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表

11E2在线视频

下一节:11E3-1

返回《Data Structures and Algorithm Design Part II》慕课在线视频列表

11E2课程教案、知识点、字幕

以下 我们就来简要地介绍gs表的具体构造算法

为了便于理解其原理

这里将整个算法划分为若干个层次

并逐层递进 逐层细化

我们首先需要引入MS子串与ss表的概念

实际上 相对于模式串中的任何一个字符P[j]

所谓的MS[j]

就是某个以P[j]为末字符的子串

而且 这个子串也同样会出现于整个模式串的尾部

当然 如果同时存在多个这样的候选

我们会在其中选择最长的那个

概括而言 所谓的MS[j]

就是终止于P[j]

同时与全串的后缀实现最长匹配的子串

当然 这个子串也有可能是空

我们来看这样一个实例

对于P[8] 也就是字符E而言

它所对应的MS子串自右向左由E、C、I、R这4个字符组成

因为这个子串与整个模式串的后缀

实现了最长的匹配

相应地 在ss表中

j所对应的那一项

其实也就是MS[j]子串的长度

在刚才这个例子中

8号字符E所对应的ss表项 也自然就应该是子串RICE的长度4

同理 对于字符P[2]而言

它所对应的MS子串为ICE

相应的ss表项 也就是这个串的长度 3

实际上 在中转的这个ss表中

已经蕴含了我们最终要计算的gs表的所有信息

因此 快速构造gs表的问题

也就自然地转化为了如何快速地构造ss表

那么 通过ss表 具体地如何构造出最终的gs表呢

无非两种情况

首先 ss[j]可能达到最大的极限 也就是j+1

此时的情况如这个图所示

也就是说 MS[j]子串足够长

以至于它就是整个模式串的一个前缀

于是 对于这个范围内的任何一个字符P[i]

一旦在扫描比对中发生失配

m-j-1也必然是一个值得考虑的位移距离

此外 都是一般的情况

也就是MS[j]子串的长度充其量不过j

此时的情况可以由下面这幅图来示意

可以看到 此时的MS[j]子串

长度还没有达到极限

于是如果将来在扫描比对的过程中在这个位置处发生首次失配

接下来一种值得考虑的位移距离自然也是m-j-1

通过以上的分析可以看到

构造gs表 关键就在于如何构造出ss表

当然 根据以上定义

即便采用蛮力策略

也是可以构造出这个表的

然而很遗憾

我们为此需要平方量级的时间

那么 这个结果能否改进呢

答案是肯定的

在我们的习题解析中

给出了具体的算法描述

以及代码实现

好消息是 采用这一新的算法

我们只需线性的时间

就足以构造出gs表

Data Structures and Algorithm Design Part II课程列表：

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找：算法

--07B1-3 查找：理解

--07B1-4 查找：实现

--07B1-5 查找：语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除：双旋

--07D3-3 删除：实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

11E2笔记与讨论

也许你还感兴趣的课程:


  1. 创新创业基础(2021秋)

  2. 好心态——如何自己造：心理健康教育(2021秋)

  3. 现代仪器分析(2021秋)

  4. 足球竞赛规则与裁判法分析(2021秋)

  5. 营房建筑学(2021秋)

  6. EDA技术与应用(2021秋)

  7. 美好生活“油”此而来：油科学概论(2021秋)

  8. 运动防护师教程(2021秋)

  9. 体育舞蹈(2021秋)

  10. 惯性导航原理(2021秋)

  11. Data Structures and Algorithm Design Part II(Self-Paced)

  12. Pharmacology(Round 1)

  13. Diagnostics(Round 1)

  14. Medical Nursing(Round 1)

  15. The Experiment for Mechanical Manufacturing Process Design and Simulation(Round 1)

  16. Chinese Language --Express to HSK(Round 1)

  17. World Arena: Facing Globalization(Self-Paced)

  18. Skills in English for General Academic Purposes(Round 1)

  19. Plato, Socrates, and the Birth of Western Philosophy(Self-Paced)

  20. Combinatorics and Algorithms Design(Self-Paced)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。