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

//在文本串中，下一個(gè)字符始終和模式串中最靠右邊匹配的字符對(duì)齊。

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