- 在线时间
- 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 算法设计的非常巧妙,初次接触时同样“吓了一跳”。5 S% E" m! z$ Y0 N7 b( l
Shift-And 与 Shift-Or 算法的原理完全一样,区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
1 K0 @. Z H- L1 Q
4 p9 }2 }* _& U) M2 DS 表示原字符串,T 表示目标串(模式串),我们要在S 中搜索T。
' D6 u& i r3 O% Y: m令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd5 D) D6 F5 J6 ^+ k
5 U" r7 v; i7 o7 s- ]* L
1,Shift-And 算法思想$ X% f0 w; G" \2 M) \
Shift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。(瞧,shift 算法的核心也是前缀匹配)。Shift 算法大量应用了位运算。
; {, d. q5 z/ n9 Z( X3 JD 是一个m 位的无符号整数:D[n-1, n-2, ..,1,0] (注意D 并不是一个数组,仅仅是一个整数,D[n-1] 表示其最高位bit)。
6 G$ W7 ^+ [+ g4 N* Q* i( d数组索引i 控制S 串的扫描,当扫描的字符S 时,D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。
: { ?. d" z) u; w3 O" b% y
4 m' b' h4 _$ C/ j3 {要使用Shift 算法,需要一个辅助表B。B 是一个字典,key 是问题域字符集中的每个字符,value 是一个n 位无符号整数,记录该字符在模式串T 的哪些位置出现。( s& z# t, l0 a% [7 G+ m
例如,字符c 在T[2] 处出现,那么B['c'] = 000100 (对于字符串,低位在左;对于B['c'],低位在右);同理,a 在T[0],T[3] 处出现,B['a'] = 001001.
5 J7 Z, Q; ? e. V" T( Z
) E- H$ S ?) |: m$ X o9 t假设当前处理到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]。
5 l7 }, F0 G+ A! G" h* l2 N所以,D = (D << 1 | 1) & B[S[i] ;
6 t* T4 Z& ` _& }7 D: _/ M! ^显然,当D[n-1]=1 时,表示T[0..n-1] 是S[0..i] 的后缀,此时找到一个T的完全匹配。; k/ D8 S& e% [: a- f( x
+ j+ [5 B# b- c) L. b! O# r
2,Shift-And 算法实现2 y- }6 J$ J% E e; K: q
Shift-And 匹配过程代码:
! c% Z9 B( |5 _. `6 h# z
1 l3 L- n, B2 w) [5 C2 C! E4 {7 ^: G9 J% u. Z! q) P5 @) _7 R! C
由于位运算在计算机中可以并行进行,每次循环的执行是常数时间的,所以上面代码段的复杂度是 O(m)。
! i* t4 b! A& [ n( F! K. h: l5 K! r$ \' h4 w4 M
3,辅助表 B
6 v" v& c+ X* \& w1 ]# t l/ v上面没有提到如何得到辅助表B。很简单,只要获得模式串T 中每个字符出现的位置。
' _6 s& M' x0 b0 p# e4 D
/ |5 I3 T0 x5 \ x2 d
" W+ J* U' ~/ K% {% C! |显然,上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
9 V1 t- g: n1 R& z* p实际上,shift 算法通常比KMP 算法的匹配速度要快,因为计算机位并行运算是非常高效的。
9 i ?+ f& }. k* S' I5 k- s
' }$ N; V. n7 ~+ f0 U5 \注意:数组B 的大小是由字符集决定的,如果字符来自ASCII 码,字符的数值范围是0~127,数组大小是128 即可;否则,可能需要更大的数组B,或者自己构建字符到整数索引之间的散列关系。
9 b6 W& K, U/ Y: f* Q; K# t6 Y5 F- P: @ \& O: F ?' O. k
4,Shift-Or 算法( H9 H! `# d$ l- l
在Shift-And 中,对掩码D 的更新:D = (D << 1 | 1) & B[S[i] ;, k/ U7 P" v( m6 h; D' F
每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S 在T[0] 处出现时,D[0] 一定要等于1,而D 向左移位后最低位是0。 E, x0 H# P( ]; `6 i
# ]( |+ A8 x+ x$ F如果将Shift-And 中核心的“与” 运算改为“或” 运算,可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。& S0 j. c6 @/ T+ C6 X
Shift-Or 与Shift-And 的唯一区别在于,在Shift-Or 中,“有效位” 是通过0(而不是1)来标识。# L1 _* J* p0 w. O0 c$ x- T
于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别,详见代码。" U0 T# k2 f$ I! [2 w1 w
! H2 p$ I o9 h$ J
Shift-And 完整代码:C++ 实现 Python 实现
+ `& G" D d+ z2 m: v1 {" |Shift-Or 完整代码:C++ 实现 Python 实现
2 t* [8 s7 i1 w+ ?
9 N% y# j% z. L! p |
zan
|