/*==================================================*/
BM 算法的改進(jìn)的算法Sunday Algorithm
BM算法優(yōu)于KMP
SUNDAY 算法描述：字符串查找算法中，最著名的兩個是KMP算法 （Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。兩個算法在最壞情 況下均具有線性的查找時間。但是在實用上，KMP算法并不比最簡單的c庫函數(shù)
strstr()快多少，而BM算法則往往比KMP算法快上3－5倍。但是BM算法還不 是最快的算法，這里介紹一種比BM算法更快一些的查找算法。 例如我們要在"substring searching algorithm"查找"search"，剛開 始時，把子串與文本左邊對齊：
substring searching algorithm
search
結(jié)果在第二個字符處發(fā)現(xiàn)不匹配，于是要把子串往后移動。但是該移動多少呢？ 這就是各種算法各顯神通的地方了，最簡單的做法是移動一個字符位置；KMP 是利用已經(jīng)匹配部分的信息來移動；BM算法是做反向比較，并根據(jù)已經(jīng)匹配的 部分來確定移動量。這里要介紹的方法是看緊跟在當(dāng)前子串之后的那個字符（第 一個字符串中的'i')。 顯然，不管移動多少，這個字符是肯定要參加下一步的比較的，也就是說，如 果下一步匹配到了，這個字符必須在子串內(nèi)。所以，可以移動子串，使子串中 的最右邊的這個字符與它對齊?，F(xiàn)在子串'search'中并不存在'i'，則說明可 以直接跳過一大片，從'i'之后的那個字符開始作下一步的比較，如下：
substring searching algorithm
search
比較的結(jié)果，第一個字符就不匹配，再看子串后面的那個字符，是'r',它在子 串中出現(xiàn)在倒數(shù)第三位，于是把子串向后移動三位，使兩個'r'對齊，如下：
substring searching algorithm
search
這次匹配成功了！回顧整個過程，我們只移動了兩次子串就找到了匹配位置， 是不是很神啊?!可以證明，用這個算法，每一步的移動量都比BM算法要大，所 以肯定比BM算法更快。
/*==================================================*/
//在文本串中，下一個字符始終和模式串中最靠右邊匹配的字符對齊。
void SUNDAY(char *text, char *patt)
{
??? size_t temp[256];
??? size_t *shift = temp;
??? size_t i, patt_size = strlen(patt), text_size = strlen(text);
??? cout << "size : " << patt_size << endl;
??? for( i=0; i < 256; i++ )
??????? *(shift+i) = patt_size+1;
??? for( i=0; i < patt_size; i++ )
??????? *(shift+unsigned char(*(patt+i))) = patt_size-i;
??? //shift['s']=6 步,shitf['e']=5 以此類推
??? size_t limit = text_size-patt_size+1;
??? for( i=0; i < limit; i += shift[ text[i+patt_size] ] )
??? {
??????? if( text[i] == *patt )
??????? {
??????????? char *match_text = text+i+1;
??????????? size_t match_size = 1;
??????????? do
??????????? {// 輸出所有匹配的位置
??????????????? if( match_size == patt_size )
??????????????????? cout << "the NO. is " << i << endl;
??????????? }
??????????? while( (*match_text++) == patt[match_size++] );
??????? }
??? }
??? cout << endl;
}
下載文檔
