透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找

美人如花

Shift-And/Shift-Or 算法和KMP 算法一样，也是线性时间复杂度的字符串匹配算法，运行时间上甚至要比KMP 算法快得多。而理解上比KMP 算法更容易一些。Shift-And/Shift-Or 算法设计的非常巧妙，初次接触时同样“吓了一跳”。
. |2 i6 T( {, h' N$ kShift-And 与 Shift-Or 算法的原理完全一样，区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
! q* z2 M+ _5 v" L6 j$ h$ w
& `( ]& h/ ~: C* R& w* w* h, h% rS 表示原字符串，T 表示目标串（模式串），我们要在S 中搜索T。
令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd
% o( D/ M1 B% j. D
5 m) N, p1 |# i8 a/ I! c1，Shift-And 算法思想
Shift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。（瞧，shift 算法的核心也是前缀匹配）。Shift 算法大量应用了位运算。
$ L$ F0 W/ q# fD 是一个m 位的无符号整数：D[n-1, n-2, ..,1,0] （注意D 并不是一个数组，仅仅是一个整数，D[n-1] 表示其最高位bit）。
数组索引i 控制S 串的扫描，当扫描的字符S 时，D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。

- |# T; }7 r( ^, [* U! z* H要使用Shift 算法，需要一个辅助表B。B 是一个字典，key 是问题域字符集中的每个字符，value 是一个n 位无符号整数，记录该字符在模式串T 的哪些位置出现。
# J, \  [& L, W. q, n$ o/ }例如，字符c 在T[2] 处出现，那么B['c'] = 000100 （对于字符串，低位在左；对于B['c']，低位在右）；同理，a 在T[0],T[3] 处出现，B['a'] = 001001.
* G, F$ b( l% ]) H6 V
# ^8 d& t4 J2 S5 n7 o* J0 O假设当前处理到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]。
1 x/ e6 [* j7 A3 C! m所以，D = (D << 1 | 1) & B[S[i］ ;
6 g% B/ {- d3 a" O/ N0 [显然，当D[n-1]=1 时，表示T[0..n-1] 是S[0..i] 的后缀，此时找到一个T的完全匹配。
5 r" ]" H1 `8 c( F/ O
8 i  ~! g& |" I, X2，Shift-And 算法实现
  t8 W) A/ V5 g7 z$ r3 UShift-And 匹配过程代码：
7 Q& ]8 [1 n# h% x

6 m/ f" p# M# s* d8 a
由于位运算在计算机中可以并行进行，每次循环的执行是常数时间的，所以上面代码段的复杂度是 O(m)。
* k& i6 U- g4 W& ~0 Z& f& o
3，辅助表 B
2 s; m  f# W+ |7 A4 }  I) ^0 x1 f上面没有提到如何得到辅助表B。很简单，只要获得模式串T 中每个字符出现的位置。

显然，上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
9 W5 U$ z3 g4 O1 P2 D* t实际上，shift 算法通常比KMP 算法的匹配速度要快，因为计算机位并行运算是非常高效的。
, [, B* t: B# }9 H  [9 L. r
注意：数组B 的大小是由字符集决定的，如果字符来自ASCII 码，字符的数值范围是0~127，数组大小是128 即可；否则，可能需要更大的数组B，或者自己构建字符到整数索引之间的散列关系。

4，Shift-Or 算法
在Shift-And 中，对掩码D 的更新：D = (D << 1 | 1) & B[S[i］ ;
3 M0 G/ a' q9 y* v6 s每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S 在T[0] 处出现时，D[0] 一定要等于1，而D 向左移位后最低位是0。
- L! ]6 U8 |* E3 G+ q
如果将Shift-And 中核心的“与” 运算改为“或” 运算，可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。
. N  O& I* \0 r$ uShift-Or 与Shift-And 的唯一区别在于，在Shift-Or 中，“有效位” 是通过0（而不是1）来标识。
/ \* k2 l/ e5 `& ^于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别，详见代码。
* z+ N# z, v$ p+ Y! C
) B( J: _4 \- P, XShift-And 完整代码：C++ 实现  Python 实现
# z' J1 L% g8 o: dShift-Or 完整代码：C++ 实现  Python 实现
+ f4 \) ^9 r5 z1 r  n' O
3 R  t2 x8 B$ ~" i! n