记得在穷举法中,每一趟比较后,无论成与不成,都将模式向右滑动一个位置,然后继续比较。有没有办法能利用之前的比较结果,使得模式滑动的更远一点呢?
在介绍经典的KMP算法前,我先介绍几个简单的滑动类算法。
Not So Naive
同名字一样,这个算法的确有点幼稚,它根据模式的前两个字符是否相同来滑动比穷举法稍长一点的距离:如果前两个字符相同,那么文本中与第二个字符不同则必然也与第一个不同;如果前两个字符不同,则与第二个相同的文本字符必然与第一个不同。
那么这两种情况下不用比较都可以断定,文本字符与模式的第一个字符肯定不相同,于是能比穷举法多滑动1个位置。
代码见下:
- void NSN(char *x, int m, char *y, int n) {
- int j, k, ell;
- /* Preprocessing */
- if (x[0] == x[1]) {
- k = 2;
- ell = 1;
- }
- else {
- k = 1;
- ell = 2;
- }
- /* Searching */
- j = 0;
- while (j <= n - m)
- if (x[1] != y[j + 1])
- j += k;
- else {
- if (memcmp(x + 2, y + j + 2, m - 2) == 0 &
- x[0] == y[j])
- OUTPUT(j);
- j += ell;
- }
- }
这个算法仅需要常数时间和空间的预处理,比较过程中,先比较模式第二个字符,然后比较其余位置,为的就在某些情况下省掉第一个字符的比较,达到滑动的目的。不过复杂度依然是O(mn)的,比起穷举法或者有轻微改善吧。
想法的确够幼稚,仅仅只考虑了两个模式字符,滑动的步子也太小,能否考虑的更多一点呢?下面请看Quick Search算法。
Quick Search
见到这个名字,不禁让人想起快速排序了,快速排序在最坏情况下是n平方的复杂度,而通常情况下速度超级快,Quick Search莫非也是这样的?没错,就是这样,这个算法在模式长度短而字母表大时,有着优异的表现,尽管它的搜索时间复杂度是O(mn)。
算法的思想是这样,如果文本中某个字符根本就没在模式中出现过,那么就不需要再去和模式中的任何一个比较;如果该字符出现过,那么为了不漏掉可能的匹配,只好与最晚出现过的位置对齐进行比较了。
代码如下:
- void preQsBc(char *x, int m, int qsBc[]) {
- int i;
- for (i = 0; i < ASIZE; ++i)
- qsBc[i] = m + 1;
- for (i = 0; i < m; ++i)
- qsBc[x[i]] = m - i;
- }
- void QS(char *x, int m, char *y, int n) {
- int j, qsBc[ASIZE];