当前课程知识点：Data Structures and Algorithm Design Part II >  11.String I >  B1.Pm >  11B1-1

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

11B1-1在线视频

下一节:11B1-2

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

11B1-1课程教案、知识点、字幕

好 接下来我们就对这一章的主角儿 也就是串匹配问题 作一概述

包括这个问题是什么 有哪些不同层次的功能要求 以及如何评测相应算法的性能

尽管我们还没有涉及到具体的算法

如果你使用Unix或Linux 那么对于grep这个命令肯定就不会陌生

这个支持正则表达式搜索的命令功能非常强大

其中最基本的一项功能就是 在某个文本中去查找特定的模式串

比如 这就是一次成功的查找 因为我们注意到people这个单词的确在上面这个句子中出现了

其实 类似的这种搜索 在当下是无处不在、无时不在的

想想你在Google或百度上 通过关键词搜索网页

就不难理解这一点

是的 对于这类搜索引擎来说

你所输入的关键词 就相当于这里的模式串

而文本串T呢

是的 它们是Internet上所有的网页

由此 我们也可以看出此类问题的一个鲜明特点

这体现在两个串的长度上

按照我们的惯例 通常都将文本串和模式串的长度分别记作n和m

通常 m本身就足够大 因此不能视作是一个常数

例如 你所搜索的关键词 通常都由几十个到一百个字符组成

另一方面 相对于已经比较大的m而言

n的规模 又要比m大上若干个甚至很多个数量级

仍然以刚才的搜索引擎为例

整个Internet上所有网页的长度之和 必然是惊人的

即便是单张网页 其规模也通常在几十到几百K

当然 我们所说的模式匹配问题

从功能和难度上 可以分为若干个递进的层次

首先 是所谓的检测 detection

也就是说 我们只关心模式串是否在文本串中出现过

至于出现在哪儿 以至于出现多少次

相对而言我们都不是那么关心

比如病毒的监控系统

更在意的是病毒的特征码在对应的邮件或文件中是否出现

只有不包含特征码的邮件或文件 才允许通过

当然 接下来的一个层次自然是定位

也就是说 如果模式串出现 我们还关心它具体出现在文本串中的哪个位置

例如 你在一份很长的网页上要查找某个特定的入口 就需要用到这样的功能

当然 通常而言 模式串有可能会出现多次

而此时 我们有可能会关心它总共出现过几次

比如 根据一份学生的花名册

借助这种功能 我们就可以统计出特定届次的学生总数

当然 再进一步地

是所谓的enumeration 枚举问题

也就是说 我们需要知道模式串在文本串中具体都出现在哪几个位置

比如在刚才的例子中 我们有可能需要进一步地确定 特定届次的学生具体是哪几位

纵观这4个层次 不难发现 其中核心的 是第2个层次

实际上 只要这个层次的问题 能够得以高效地求解

后续的问题 也自然可以迎刃而解

因此 这一层次的问题 也是我们在这一章中将主要讨论的范畴

鉴于串匹配问题的特殊性 在给出具体的算法之前

我们需要首先来确定 应该如何地测量和评判 此类算法的性能

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

11B1-1笔记与讨论

也许你还感兴趣的课程:


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