匹配算法一

现在就该位运算出场了，对，这个算法的思路是很笨，但是我位运算的效率高呀，事先我算出字母表中每个字符在模式中出现的位置，用位的方式存在整数里，出现的地方标为0，不出现的地方标为1，这样总共使用σ个整数；同样，我用一个整数来表示升级状态，某个级别有人就标为0，没人就标为1，整个系统升级就恰好可以用“移位”来进行，当检查位置的时候只需要与表示状态的整数“或”1次，所以整个算法就成O(n)了。Shift-Or算法名字就是这样来的。

有一个地方很奇怪，0和1的设定和通常的习惯相反呀，习惯上，喜欢把存在设为1，不存在设为0的。不过这里没有办法，因为移位新移出来的是0。

这时我们来看代码就容易理解多了： 1. #define WORDSIZE sizeof(int)*8

2. #define ASIZE 256

3.

4. int preSo(const char *x, int m, unsigned int S[]) {

5. unsigned int j, lim;

6. int i;

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. }

16.

17. void SO(const char *x, int m, const char *y, int n) {

18. unsigned int lim, state;

19. unsigned int S[ASIZE];

20. int j;

21. if (m > WORDSIZE)

22. error(\

23.

24. /* Preprocessing */

25. lim = preSo(x, m, S);

26.

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算法的描述还是很难懂的，如果对着那段说明去看代码，有点不知所云的感觉。我还是直接对着代码才想出这个升级的比喻来。

四、可以滑动多远

记得在穷举法中，每一趟比较后，无论成与不成，都将模式向右滑动一个位置，然后继续比

较。有没有办法能利用之前的比较结果，使得模式滑动的更远一点呢？

在介绍经典的KMP算法前，我先介绍几个简单的滑动类算法。

Not So Naive 同名字一样，这个算法的确有点幼稚，它根据模式的前两个字符是否相同来滑动比穷举法稍长一点的距离：如果前两个字符相同，那么文本中与第二个字符不同则必然也与第一个不同；如果前两个字符不同，则与第二个相同的文本字符必然与第一个不同。

那么这两种情况下不用比较都可以断定，文本字符与模式的第一个字符肯定不相同，于是能比穷举法多滑动1个位置。

代码见下：

1. void NSN(char *x, int m, char *y, int n) {

2. int j, k, ell;

3.

4. /* Preprocessing */

5. if (x[0] == x[1]) {

6. k = 2;

7. ell = 1;

8. }

9. else {

10. k = 1;

11. ell = 2;

12. } 13.

14. /* Searching */

15. j = 0;

16. while (j <= n - m)

17. if (x[1] != y[j + 1])

18. j += k;

19. else {

20. if (memcmp(x + 2, y + j + 2, m - 2) == 0 &

21. x[0] == y[j])

22. OUTPUT(j);

23. j += ell;

24. } 25. } 26. 27.

这个算法仅需要常数时间和空间的预处理，比较过程中，先比较模式第二个字符，然后比较其余位置，为的就在某些情况下省掉第一个字符的比较，达到滑动的目的。不过复杂度依然是O(mn)的，比起穷举法或者有轻微改善吧。

想法的确够幼稚，仅仅只考虑了两个模式字符，滑动的步子也太小，能否考虑的更多一点呢？下面请看Quick Search算法。

Quick Search

见到这个名字，不禁让人想起快速排序了，快速排序在最坏情况下是n平方的复杂度，而通常情况下速度超级快，Quick Search莫非也是这样的？没错，就是这样，这个算法在模式长度短而字母表大时，有着优异的表现，尽管它的搜索时间复杂度是O(mn)。

算法的思想是这样，如果文本中某个字符根本就没在模式中出现过，那么就不需要再去和模式中的任何一个比较；如果该字符出现过，那么为了不漏掉可能的匹配，只好与最晚出现过的位置对齐进行比较了。

代码如下：

1. void preQsBc(char *x, int m, int qsBc[]) {

2. int i;