- 在线时间
- 3 小时
- 最后登录
- 2015-5-5
- 注册时间
- 2015-4-8
- 听众数
- 10
- 收听数
- 0
- 能力
- 0 分
- 体力
- 92 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 43
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 26
- 主题
- 14
- 精华
- 0
- 分享
- 0
- 好友
- 7
升级   40% TA的每日心情 | 慵懒 2015-5-5 09:46 |
|---|
签到天数: 10 天 [LV.3]偶尔看看II
- 自我介绍
- 撒
 |
Shift-And/Shift-Or 算法和KMP 算法一样,也是线性时间复杂度的字符串匹配算法,运行时间上甚至要比KMP 算法快得多。而理解上比KMP 算法更容易一些。Shift-And/Shift-Or 算法设计的非常巧妙,初次接触时同样“吓了一跳”。
& o( v+ ~( W0 }1 R! [) EShift-And 与 Shift-Or 算法的原理完全一样,区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
0 w& n/ S* B; U* e
) d$ {' W. Y6 z* i7 U- }S 表示原字符串,T 表示目标串(模式串),我们要在S 中搜索T。& `8 S% F0 X- n7 t
令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd; ]( I; @7 ?+ s$ L% l6 K
3 J5 ^5 O( `( k2 q" X% }1,Shift-And 算法思想
3 [4 R- ~) R: }9 q. ]' w# AShift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。(瞧,shift 算法的核心也是前缀匹配)。Shift 算法大量应用了位运算。
* M' N4 g; g/ o p8 k: y; |' cD 是一个m 位的无符号整数:D[n-1, n-2, ..,1,0] (注意D 并不是一个数组,仅仅是一个整数,D[n-1] 表示其最高位bit)。
# }' a4 U4 T6 F' a: R数组索引i 控制S 串的扫描,当扫描的字符S 时,D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。- e% Q0 F2 ]) y; R3 x/ u
7 V+ p0 a/ A4 I8 K% C/ }! i" c
要使用Shift 算法,需要一个辅助表B。B 是一个字典,key 是问题域字符集中的每个字符,value 是一个n 位无符号整数,记录该字符在模式串T 的哪些位置出现。/ i+ m! j2 P& {) b0 [" `7 g
例如,字符c 在T[2] 处出现,那么B['c'] = 000100 (对于字符串,低位在左;对于B['c'],低位在右);同理,a 在T[0],T[3] 处出现,B['a'] = 001001.
" U+ b. \. Q( p% O9 [9 B" M) q/ F
/ b8 J. U! _- f7 P* |. ~假设当前处理到S,需要对D 进行更新。由于D[j] (0<j<n) 标识T[0..j] 是否是S[0..i] 的后缀,所以D[j]=1 当且仅当更新前的D[j-1]=1 并且S==T[j];D[0] 是边界情况,D[0]=1 当且仅当S==T[0]。 u# i# Q1 P; a$ j7 M
所以,D = (D << 1 | 1) & B[S[i] ;0 c" [# I% g4 e8 C* U, [/ j
显然,当D[n-1]=1 时,表示T[0..n-1] 是S[0..i] 的后缀,此时找到一个T的完全匹配。- Y. s5 { A5 r3 b
4 ^' l: |- C/ k# I
2,Shift-And 算法实现$ `; n+ z4 U& C" ?' X
Shift-And 匹配过程代码:* o# V T$ K1 Q% N4 x3 c0 a* r
2 F; L6 x- Y D
7 x1 Z& y h8 V; p, Z4 I由于位运算在计算机中可以并行进行,每次循环的执行是常数时间的,所以上面代码段的复杂度是 O(m)。
4 v* \5 I" ~# N0 J- M- C# y6 r
& F" f, k9 C: ~8 x# p' `* W# D3,辅助表 B
' v$ @( o& W, B, e" w$ u! I) p上面没有提到如何得到辅助表B。很简单,只要获得模式串T 中每个字符出现的位置。
" A# _$ F- }4 g( y# n
$ v6 { e0 E$ }% y+ ^, s4 G9 x; Q4 y" q, t+ g" v3 J
显然,上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
! o) [- w" J- ?: K实际上,shift 算法通常比KMP 算法的匹配速度要快,因为计算机位并行运算是非常高效的。
- b- ^8 S% h+ a* d, A3 v1 y: K! F m3 u& O. D
注意:数组B 的大小是由字符集决定的,如果字符来自ASCII 码,字符的数值范围是0~127,数组大小是128 即可;否则,可能需要更大的数组B,或者自己构建字符到整数索引之间的散列关系。0 ~7 u2 k3 U1 p- r$ u( t
& `, W! c& i8 M( }2 \4,Shift-Or 算法/ {. z+ A! j$ h" m! I, G
在Shift-And 中,对掩码D 的更新:D = (D << 1 | 1) & B[S[i] ;6 Q" w9 y6 b: p @ [2 {
每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S 在T[0] 处出现时,D[0] 一定要等于1,而D 向左移位后最低位是0。
+ z! m s% M0 U3 q' ?- G0 R6 H" b/ E3 f
如果将Shift-And 中核心的“与” 运算改为“或” 运算,可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。* h( g7 J* q, [
Shift-Or 与Shift-And 的唯一区别在于,在Shift-Or 中,“有效位” 是通过0(而不是1)来标识。) O) |7 ]0 n& {1 a3 ], G9 @
于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别,详见代码。
8 J0 K- o- ^& s, F# A0 @
* m: y0 t; j/ q+ DShift-And 完整代码:C++ 实现 Python 实现+ n! c0 q. \ ^0 n* o' G0 b2 k, j
Shift-Or 完整代码:C++ 实现 Python 实现9 \+ ]2 v! U) `
, S+ P$ _& o8 H+ D3 \
|
zan
|