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)。所以，可以移動子串，使子串中的最右邊的這個字符與它對齊。現(xiàn)在子串'search'中并不存在'i'，則說明可以直接跳過一大片，從'i'之后的那個字符開始作下一步的比較，如下圖：
substring searching algorithm
search
^
比較的結(jié)果，第一個字符就不匹配，再看子串后面的那個字符，是'r',它在子串中出現(xiàn)在倒數(shù)第三位，于是把子串向前移動三位，使兩個'r'對齊，如下：
substring searching algorithm
search
^
哈！這次匹配成功了！回顧整個過程，我們只移動了兩次子串就找到了匹配位置，是不是很神啊?!可以證明，用這個算法，每一步的移動量都比BM算法要大，所以肯定比BM算法更快。
算法是網(wǎng)上的，等下寫個delphi的子程。
已經(jīng)搞定了：
例程放出來，其實這個子程是為了寫一個內(nèi)存搜索器寫的，速度如何我還沒測試，回去和delphi的pos比較下．pos是用匯編寫的，程序用到了pos函數(shù)，但是由于向前進(jìn)的速度比較快，應(yīng)該稍微快點的．程序直接保存為check.dpr，可以直接運行．使用本篇文章的請標(biāo)明出處：灰色代碼
program check;
{$APPTYPE CONSOLE}
uses
SysUtils,
TlHelp32,
windows;
var
s_string :array [0..32] of char; //關(guān)鍵詞
s:array [0..256]of char ;//字符集
len,i,flag:Integer;
p:pointer;
function comp(p:Integer):Boolean;
var
i:Integer;
begin
Result:=true;
for i:=0 to len-1 do
if s[p+i]<>s_string[i] then
begin
Result:=False;
Exit;
end;
end;
begin
{ TODO
-oUser -cConsole Main : Insert code here }
i:=0;
s:='subatring searching algorithm';
p:=@s[0];//這些沒用,我是測試怎么取到從數(shù)組第i個字符開始的后n個字符的
Writeln(pchar(p));
Writeln('輸入要搜索的字符：');
Readln(s_string);
len:=strlen(s_string);
Writeln(s_string+'長度：'+inttostr(len));
while
comp(i)=false
do//沒找到
begin
if
i>strlen(s) then break;//大于定義的字符集最大長度 退出
writeln(s[i+len]);//這句也沒用，測試用的
if
Pos(s[i+len],s_string)<>0 then
//第i＋len個字符在要找的字符串里
begin
i:=i+1+len-pos(s[i+len],s_string); //對齊相同的
end
else
begin//第i＋len個字符不在要找的字符串里，直接后移
i:=i+len+1;
end;
end;
if comp(i)=true then
begin
Writeln('成功找到該字符串');
windows.Beep(500,5);
readln;
end
else
begin
Writeln('沒有找到該字符串');
windows.Beep(500,5);
readln;
end;
end.
