位运算经常能做出一些不可思议的事情来，例如不用临时变量要交换两个数该怎么做呢？一个没接触过这类问题的人打死他也想不出来。如果拿围棋来做比喻，那么位运算可以喻为编程中的“手筋”。
按位的存储方式能提供最大的存储空间利用率，而随着空间被压缩的同时，由于CPU硬件的直接支持，速度竟然神奇般的提升了。举个例子，普通的数组要实现移位操作，那是O(n)的时间复杂度，而如果用位运算中的移位，就是一个指令搞定了。
KR算法
KR算法之前第一章介绍中说是利用哈希，原文这么介绍的。而我的看法是，哈希只是一个幌子。这个算法的基本步骤同穷举法一样，不同在于每趟比较前先比较一下哈希值，hash 值不同就不必比较了。而如果hash值无法高效计算，这样的改进甚至还不如不改进呢。你想想，比较之前还要先计算一遍hash值，有计算的功夫，直接比都比完了。
KR算法为了把挨个字符的比较转化为两个整数的比较，它把一个m长度的字符串直接当成一个整数来对待，以2为基数的整数。这样呢，在第一次算出这个整数后，以后每次移动窗口，只需要移去最高位，再加上最低位，就得出一个新的hash值。但是m太大，导致超出计算机所能处理的最大整数怎么办？不用担心，对整数最大值取模，借助模运算的特性，一切可以完美的进行。而且由于是对整数最大值取模，所以取模这一步都可以忽略掉。
这是KR算法的代码：
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
void KR(char *x, int m, char *y, int n) {
int d, hx, hy, i, j;
/* Preprocessing */
/* computes d = 2^(m-1) with
the left-shift operator */
for (d = i = 1; i < m; ++i)
d = (d<<1);
for (hy = hx = i = 0; i < m; ++i) {
hx = ((hx<<1) + x[i]);
hy = ((hy<<1) + y[i]);
}
/* Searching */
j = 0;
while (j <= n-m) {
if (hx == hy && memcmp(x, y + j, m) == 0)
OUTPUT(j);
hy = REHASH(y[j], y[j + m], hy);
++j;
}
}
我们可以看到，KR算法有O(m)复杂度的预处理的过程，总感觉它的预处理没有反映出模式本身的特点来，导致它的搜索过程依然是O(mn)复杂度的，只不过一般情况下体现不出来，在"aaaaaaaaaaaaaaaaaaaaaaaaa"中搜"aaaaa"就知道KR多慢了。
总的来说，KR算法比穷举强一点，比较次数的期望值是O(m+n)。
Shift Or 算法
为了最大限度的发挥出位运算的能力，Shift Or算法就有了一个最大缺陷：模式不能超过机器字长。按现在普遍的32位机，机器字长就是32，也就是只能用来匹配不大于32个字符的模式。而带来的好处就是匹配过程是O(n)时间复杂度的，达到自动机的速度了。而预处理所花费的时间与空间都为O(m+σ)，比自动机少多了。
我们来看看它怎么巧妙的实现“只看一遍”的：
假设我们有一个升级系统，总共有m个级别。每一关都会放一个新人到第0级上，然后对于系统中所有的人，如果通过考验，升一级，否则，咔嚓掉。而对于升到最高级的人，那说明他连续通过了m次考验，这就是我们要选拔的人。
KR算法的思路就是上面的升级规则，给出的考验就是你的位置上的字符与给出的文本字符是否一致。升
满级了，说明在连续m个位置上与不断给出的文本字符一致，这也就是匹配成功了。
明白了这个思路后，疑问就开始出来了：检查哪些位置与文本字符一致，需要m次吧？那么整个算法就是O(mn)了？
现在就该位运算出场了，对，这个算法的思路是很笨，但是我位运算的效率高呀，事先我算出字母表中每个字符在模式中出现的位置，用位的方式存在整数里，出现的地方标为0，不出现的地方标为1，这样总共使用σ个整数；同样，我用一个整数来表示升级状态，某个级别有人就标为0，没人就标为1，整个系统升级就恰好可以用“移位”来进行，当检查位置的时候只需要与表示状态的整数“或”1次，所以整个算法就成O(n)了。Shift-Or算法名字就是这样来的。
有一个地方很奇怪，0和1的设定和通常的习惯相反呀，习惯上，喜欢把存在设为1，不存在设为0的。不过这里没有办法，因为移位新移出来的是0。
这时我们来看代码就容易理解多了：
#define WORDSIZE sizeof(int)*8
#define ASIZE 256
int preSo(const char *x, int m, unsigned int S[]) {
unsigned int j, lim;
int i;
for (i = 0; i < ASIZE; ++i)
S[i] = ~0;
for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
S[x[i]] &= ~j;
lim |= j;
}
lim = ~(lim>>1);
return(lim);
}
void SO(const char *x, int m, const char *y, int n) {
unsigned int lim, state;
unsigned int S[ASIZE];
int j;
if (m > WORDSIZE)
error("SO: Use pattern size <= word size");
/* Preprocessing */
lim = preSo(x, m, S);
/* Searching */
for (state = ~0, j = 0; j < n; ++j) {
字符串长度不能超过32位state = (state<<1) | S[y[j]];
if (state < lim)
OUTPUT(j - m + 1);
}
}
代码中lim变量其实就是一个标尺，例如出现最高级的状态是01111111，那么lim就成了10000000，因此只要小于lim，就表示最高级上的0出现了。
原文中对Shift-Or算法的描述还是很难懂的，如果对着那段说明去看代码，有点不知所云的感觉。我还是直接对着代码才想出这个升级的比喻来。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。