当前课程知识点：Data Structures and Algorithm Design Part II >  11.String I >  B2.brute-force >  11B2-2

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

11B2-2在线视频

下一节:11B2-3

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

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

上述的蛮力算法 至少有两种实现的版本

因为由它们 可以很方便地分别导出后续更为高效的算法

因此 我们这里不妨对它们都作一介绍

这两个版本对外的接口都是一样的

按照我们这里的命名习惯 入口参数P和T 分别指向模式串和文本串

而且在这里 我们采用了最为基本的字符串表示方法

而且约定 在每一个串的末尾 都有一个数值为0的哨兵

而且按照我们一贯的约定 串长并不计入尾部的这个哨兵

为了分别指示在模式串和文本串中当前的字符位置

这里还需要使用两个整数 i和j

在后一版本中 我们同样会用到这样的两个整数

但它们的语义却不尽相同

这也是前后两个版本的本质区别所在

如这个图所示

在这里 i和j所指示的 分别是当前主串中与模式串中 接受比对的那样一对字符

因此 二者同时初始化为0 也再自然不过了

算法将两个串逐位对齐 并进行比对的过程

兑现为这样一个while循环

正如刚才所介绍的

在每一对齐位置 我们都需要将文本串与模式串的当前字符取出

并将二者作一比对

如果相等 则令两个整数携手并进

从而分别指向下一对字符

否则 则意味着失配

你应该记得 此时我们应该令模式串相对于文本串向后滑动一个字符

并重新对齐

为此 对于j而言我们只需令其复位为0

那么 文本串的指针i呢

为了确定指针i的更新方法 我们需要重新回到这幅图

这幅图告诉我们 在算法的任何一个时刻

模式串相对于文本串的对齐位置 都是由i和j的差来指定的

因此 既然j的更新 等效于其在数值上减少了j

i的更新 也就应该等效于其在数值上减少j-1

如果能悟到这一点

也就自然可以理解 在这里对i的更新方法了

总而言之 这里的if相当于在保持相对位置不变的情况下

去比较每一对字符

而else才对应于P与T之间的相对滑动

我们再来考察这个循环的退出条件

不难看出 有两种情况

无论是j越过了它的上界m

或者i越过了它的上界n

这个循环都会随即退出

你能看出 这两种情况分别对应于什么吗

没错 分别对应于整体的匹配成功与否

为此我们需要注意到这个算法的另一个不变性

考察这里作为指针的整数j

实际上 在整个算法过程中的任何一个时刻

j的数值就对应于在当前的对齐位置下 已经做过的成功比对次数

因此 一旦j达到它的上界m

也就意味着模式串中的这m个字符 都得到了匹配

这难道不正是一次整体的匹配吗

在这种情况下 我们返回i-j 是再自然不过的了

因为通过它 可以向这个算法的上层调用者报告

就在文本串的这个位置

发现了一处完全匹配

我们再来考虑i越界的情况

因为i是逐一增加的

因此 它在越界的时候必然会恰好等于n

而此时的j依然处于合法的区间

综合这两个条件不难得知

而在这一分支退出时 返回值i-j必然会大于n-m

我们知道n-m应该是模式串相对于文本串而言 能够对齐的最靠右、也是最后一个位置

因此 这时的i-j既然已经超越了这个合法的位置

这个算法的上层调用者自然就可以据此断定 整个匹配是以失败告终的

总而言之 在这里通过简明地返回对齐位置i-j 就可以准确地向算法的上层调用者报告

究竟是匹配成功还是失败

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

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