字符串匹配算法(四)可以滑动多远.pdfVIP

得在穷举法中，每一趟比较后，无论成与不成，都将模式向右滑动一个位置，然后继续比较。有没有办 法能利用之前的比较结果，使得模式滑动的更远一点呢？ 在介绍经典的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; 3. 4. for (i = 0; i ASIZE; ++i) 5. qsBc[i] = m + 1; 6. for (i = 0; i m; ++i) 7. qsBc[x[i]] = m - i; 8. } 9. 10. 11. void QS(char *x, int m, char *y, int n) { 12. int j, qsBc[ASIZE]; 13. 14. /* Preprocessing */ 15. preQsBc(x, m, qsBc); 16. 17. /* Searching */ 18. j = 0; 19. while (j = n - m) { 20. if (memcmp(x, y + j, m) == 0) 21. OUTPUT(j); 22. j += qsBc[y[j + m]]; /* shift */ 23. } 24. } 25. 26. 理解这个算法，请看