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

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

11A-2在线视频

下一节:11A-3

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

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

为了便于接下来的讨论

我们首先来统一关于串的一些术语和记法

一般地 如果一个名为S的字符串 由n个字符构成

我们就将所有的字符 从前至后 编号为0至n-1

并按照我们的惯例 记作S[0,n)

而串中秩为k的字符 也相应地记作S[k]

于是我们就可以定义 什么叫做两个字符串相等

有两个条件 首先是它们的长度相等

其次 所有的字符 也必须捉对地相等

也就是说 二者必须一模一样

接下来的一个重要概念是子串 sub-string

对于任何一个字符串S而言

由i和k所指定的那个子串 也就是从秩为i的那个字符开始 连续的k个字符

以这幅图为例

如果整体为字符串S 那么这里所指的子串 也就是其中的这样一段

可以看到 其中字符的秩 介于i与i+k之间

接下来 所谓的前缀 prefix 是子串的一个特例

具体来说 所谓长度为k的前缀 也就是起始于首字符的前k个字符

对称地 我们也可以定义所谓的后缀 suffix

具体地 所谓长度为k的后缀 也就是终止于末元素的最靠后的k个字符

不难验证 所谓起始于i 长度为k的子串

也就是在长度为i+k的前缀中 长度为k的后缀

当然 这些定义中所涉及的所有参数 都是合法的

为了节省时间 我们将不再每次都专门地对此作说明

当然 有一种边界情况在此需要专门说明

也就是说 串长n有可能是0

此时 我们也称之为空串

请注意 空串与由空格组成的串 并不是一回事儿

空串 有别于其他各种串的特征 就是它的长度为0

为了简化后续的讨论 我们不妨在此统一约定

空串是任何串的子串 也是任何串的前缀与后缀

同时 作为另外一种边界的情况

我们也统一约定 任何串也是它自身的子串 以及前缀和后缀

反过来 长度严格小于原串的子串、前缀与后缀 也称作真子串、真前缀与真后缀

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

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