比Boyer-Moore更快的字符串查找算法
                                       
字符串查找算法中，最著名的兩個是KMP算法（Knuth-Morris-Pratt)和BM算法（
Boyer-Moore)。兩個算法在最壞情況下均具有線性的查找時間。但是在實用上，K
MP算法并不比最簡單的c庫函數strstr()快多少，而BM算法則往往比KMP算法快上3
－5倍。但是BM算法還不是最快的算法，這里介紹一種比BM算法更快一些的查找算
法。
例如我們要在"substring searching algorithm"查找"search"，剛開始時，把子
串與文本左邊對齊，
substring searching algorithm
search
^
結果在第二個字符處發現不匹配，于是要把子串往后移動。但是該移動多少呢？這
就是各種算法各顯神通的地方了，最簡單的做法是移動一個字符位置；KMP是利用
已經匹配部分的信息來移動；BM算法是做反向比較，并根據已經匹配的部分來確定
移動量。這里要介紹的方法是看緊跟在當前子串之后的那個字符（上圖中的'i')。
顯然，不管移動多少，這個字符是肯定要參加下一步的比較的，也就是說，如果下
一步匹配到了，這個字符必須在子串內。所以，可以移動子串，使子串中的最右邊
的這個字符與它對齊。現在子串'search'中并不存在'i'，則說明可以直接跳過一
大片，從'i'之后的那個字符開始作下一步的比較，如下圖：
substring searching algorithm
       search
       ^
比較的結果，第一個字符就不匹配，再看子串后面的那個字符，是'r',它在子串中
出現在倒數第三位，于是把子串向前移動三位，使兩個'r'對齊，如下：
substring searching algorithm
          search

哈！這次匹配成功了！回顧整個過程，我們只移動了兩次子串就找到了匹配位置，
是不是很神啊?!可以證明，用這個算法，每一步的移動量都比BM算法要大，所以肯
定比BM算法更快。
下面是這個算法的c代碼。注意我假設了每個字符的值都介于0-127之間（即純asc
ii碼）。

char *qsearch(const char *text, int n, const char *patt, int m)
{
// get the length of the text and the pattern, if necessary
if (n < 0)
  n = strlen(text);
if (m < 0)
  m = strlen(patt);
if (m == 0)
  return (char*)text;

// construct delta shift table
int td[128];
for (int c = 0; c < 128; c++)
  td[c] = m + 1;
const char* p;
for (p=patt; *p; p++)
  td[*p] = m - (p - patt);

// start searching...
const char *t, *tx = text;

// the main searching loop
while (tx + m <= text + n) {
  for (p = patt, t = tx; *p; ++p, ++t) {
   if (*p != *t)  // found a mismatch
    break;
  }
  if (*p == 0)   // Yes! we found it!
   return (char*)tx;
  tx += td[tx[m]];  // move the pattern by a distance
}
return NULL;
}