当前课程知识点:Data Structures and Algorithm Design Part II > 11.String II > D3.BM_BC.constructing_bc[] > 11D3
返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part II》慕课在线视频列表
这里 我们就给出bc表一种可能的构造算法
我们知道 bc表需要为字母表中的每一个字符准备一个表项
二者的长度相等
因此 我们首先就要为它开辟出这样的一个空间
比如 长度为256
接下来 我们需要通过一趟循环遍历
将所有表项的初值
统一设为-1
如果你能从设置哨兵的角度来看待这一操作
那么就可以非常清晰地理解这步操作的涵义
是的 这样等效于将所有的表项都统一地指向那个通配的哨兵
接下来又是一趟循环
这一个循环将遍历整个模式串
逐一地枚举出其中的每一个字符
并用这个字符所对应的秩
来更新对应的bc表项
请注意 即便同一个字符在模式串中出现了多次
按照这种方法
依然可以按照我们的要求正确地设置好对应的bc表项
其原因在于
我们这里采用的是自左向右的扫描次序
而整个计算过程采用的正是画家的策略
也就是说 在画布上的任何一个位置
后画上去的颜料必然会覆盖掉此前所画的颜料
而当画家作画完毕时
每一个位置所体现的颜色
是取决于在那个位置上留下的最后一笔
因此就bc表而言
任何一个字符所对应表项的最终取值
是取决于它在模式串中出现位置最靠后的那一次
可以看到
在空间上 这里的消耗主要来自于
bc表本身
因此 空间复杂度应该线性正比于字母表的规模
构造bc表所需的时间主要花费在两次for循环上
前者 依然线性正比于字母表的规模
而后者 则线性正比于模式串的长度
在这里 有一个非常有趣的问题
也就是说
第一趟循环实际上是可能省略的
而且这种方法是通用的
可以适用于任何散列表的初始化
如果你对此感兴趣
同样可以参考我们所提供的习题解析中的对应习题
那么 使用如此构造出来的bc表
BM算法本身的性能
又是怎样的呢
-A.introduction
--07A-1
--07A-2
--07A-3
--07A-4
--07A-5
-A.introduction--Homework
-B1.BST : search
--07B1-1
-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
-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
-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
-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
-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
-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
-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
-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
-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