字符串匹配算法（三）位运算的魔法——KR与SO

位运算经常能做出一些不可思议的事情来，例如不用临时变量要交换两个数该怎么做呢？一个没接触过这类问题的人打死他也想不出来。如果拿围棋来做比喻，那么位运算可以喻为编程中的“手筋”。

按位的存储方式能提供最大的存储空间利用率，而随着空间被压缩的同时，由于CPU硬件的直接支持，速度竟然神奇般的提升了。举个例子，普通的数组要实现移位操作，那是O(n)的时间复杂度，而如果用位运算中的移位，就是一个指令搞定了。

KR算法

KR算法之前第一章介绍中说是利用哈希，原文这么介绍的。而我的看法是，哈希只是一个幌子。这个算法的基本步骤同穷举法一样，不同在于每趟比较前先比较一下哈希值，hash值不同就不必比较了。而如果hash值无法高效计算，这样的改进甚至还不如不改进呢。你想想，比较之前还要先计算一遍hash值，有计算的功夫，直接比都比完了。

KR算法为了把挨个字符的比较转化为两个整数的比较，它把一个m长度的字符串直接当成一个整数来对待，以2为基数的整数。这样呢，在第一次算出这个整数后，以后每次移动窗口，只需要移去最高位，再加上最低位，就得出一个新的hash值。但是m太大，导致超出计算机所能处理的最大整数怎么办？不用担心，对整数最大值取模，借助模运算的特性，一切可以完美的进行。而且由于是对整数最大值取模，所以取模这一步都可以忽略掉。

这是KR算法的代码：

1. #defineREHASH(a,b,h)((((h)-(a)*d)<<1)+(b))
3. voidKR(char*x,intm,char*y,intn){
4. intd,hx,hy,i,j;
6. /*Preprocessing*/
7. /*computesd=2^(m-1)with
8. theleft-shiftoperator*/
9. for(d=i=1;i<m;++i)
10. d=(d<<1);
12. for(hy=hx=i=0;i<m;++i){
13. hx=((hx<<1)+x[i]);
14. hy=((hy<<1)+y[i]);
15. }
17. /*Searching*/
18. j=0;
19. while(j<=n-m){
20. if(hx==hy&&memcmp(x,y+j,m)==0)
21. OUTPUT(j);
22. hy=REHASH(y[j],y[j+m],hy);
23. ++j;
24. }
26. }

我们可以看到，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。

这时我们来看代码就容易理解多了：

1. #defineWORDSIZEsizeof(int)*8
2. #define ASIZE 256
4. intpreSo(constchar*x,intm,unsignedintS[]){
5. unsignedintj,lim;
6. inti;
7. for(i=0;i<ASIZE;++i)
8. S[i]=~0;
9. for(lim=i=0,j=1;i<m;++i,j<<=1){
10. S[x[i]]&=~j;
11. lim|=j;
12. }
13. lim=~(lim>>1);
14. return(lim);
15. }
17. voidSO(constchar*x,intm,constchar*y,intn){
18. unsignedintlim,state;
19. unsignedintS[ASIZE];
20. intj;
21. if(m>WORDSIZE)
22. error("SO:Usepatternsize<=wordsize");
24. /*Preprocessing*/
25. lim=preSo(x,m,S);
27. /*Searching*/
28. for(state=~0,j=0;j<n;++j){
29. state=(state<<1)|S[y[j]];
30. if(state<lim)
31. OUTPUT(j-m+1);
32. }
33. }

代码中lim变量其实就是一个标尺，例如出现最高级的状态是01111111，那么lim就成了10000000，因此只要小于lim，就表示最高级上的0出现了。

原文中对Shift-Or算法的描述还是很难懂的，如果对着那段说明去看代码，有点不知所云的感觉。我还是直接对着代码才想出这个升级的比喻来。