当前课程知识点：Data Structures and Algorithm Design Part II >  11.String II >  D1.BM_BC.begin_with_the_end >  11D1-2

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

11D1-2在线视频

下一节:11D1-3

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

11D1-2课程教案、知识点、字幕

让我们将视线拉回到蛮力算法

你应该记得 蛮力算法一次典型的运行过程

可以表示为这样一幅图

是的 如果将文本串固定在这里

那么 这些就是模式串在不同对齐位置处的历史快照

事实上 模式串在每一个对齐位置的故事 都是类似的

首先 要经过若干次成功的比对

在这里 用绿色的线条来表示

而接下来 总是一次失败的比对

此后 在下一位置的故事依然

该算法也需要经过若干次成功的比对

然后终止于失败的比对

而在接下来的第三次、第四次、第五次等等等等

各次对齐中 也同样都是要经过若干次成功的比对

并终止于一次失败的比对

因此 就局部的每一次对齐而言

我们都需要经过若干次的成功

并终止于一次失败

请注意 在每次对齐中尽管只有一次失败

但却足以确定相应的对齐位置是无效的

事实上 只有最后一次对齐位置才有可能是成功的

因此 就整体而言恰好与刚才局部的模式相反

多次失败 以及至多一次的成功

因此 如果我们着眼于改进蛮力算法

那么 我们的目标与其说是要加速匹配

不如说是要加速失败

或更准确地讲

要尽可能快速地、低成本地排除掉无效的对齐位置

事实上 KMP等算法就是这样

你应该记得

KMP会聪明地排除掉其中的若干个 甚至是大量的对齐位置

从而大大地节省计算的成本

甚至从某种意义上讲

我们或许能够做得比KMP还要出色

正如我们刚才所指出的

就排除某个对齐位置而言

相应的那些成功的比对

并不重要

而在这个意义上起实质作用的 反而是那些失败的比对

如果真的像刚才说的那样

我们总是需要在排除多个无效的对齐位置之后

才能够确定最终有效的对齐位置

那么 我们反倒应该更加期盼这种失败的比对出现得更早

比如 按照这种思路的一种极端情况就是

我们或许可能只做这些失败的比对

就足以排除掉相应的对齐位置

无论是它

还是它

以及它

它

诸如此类

正如我们在习题解析中所指出的那样

为了排除掉一个对齐位置

我们平均只需做常数次比对

而且在理想平均的情况下

你甚至不必去关心

哪个字符更有可能首先失败

而只需按部就班地从前向后、自左而右地依次比对就可以了

是的 如果我们的关注力只停留于单个的比对位置

那么固然如此

但是 倘若我们将所有的对齐位置作为一个整体来考虑

我们就会发现 实际上 在每一个对齐位置处

按照什么样的次序去尝试对比各字符

却十分敏感而关键

我们的建议是 你或许应该优先去比对那些靠后、乃至最靠后的字符

也就是说

与我们常规的做法恰恰相反

或许你应该更多地去关注教训

是的 如果教训的确不能避免的话

或许我们应该让它更早地暴露出来

或者再准确地讲

应该让更大的教训 更早地暴露出来

那么 为什么就串匹配算法而言

在越靠后的位置所获得的教训

所具有的价值越高呢

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

11D1-2笔记与讨论

也许你还感兴趣的课程:


  1. 思维与逻辑——应该如何讲理(2021秋)

  2. 采油工程(2021秋)

  3. 分数域信号与信息处理及其应用(2021秋)

  4. 工程热力学（下）(2021秋)

  5. 数学实验(2021秋)

  6. 飞机推进系统原理(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)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。