|
|
发表于 2012-5-6 17:18:11
|
显示全部楼层
话说 字符串搜索是 竞赛的热门题型 网上很多的
原文地址：
http://hi.baidu.com/blackcode/bl ... 3621f3b211c7bd.html
SUNDAY 算法描述：
字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的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算法更快。
算法是网上的，等下写个delphi的子程。
已经搞定了：
例程放出来，其实这个子程是为了写一个内存搜索器写的，速度如何我还没测试，回去和delphi的pos比较下．pos是用汇编写的，程序用到了pos函数，但是由于向前进的速度比较快，应该稍微快点的．程序直接保存为check.dpr，可以直接运行．使用本篇文章的请标明出处：灰色代码
program check;
{$APPTYPE CONSOLE}
uses
SysUtils,
TlHelp32,
windows;
var
s_string :array [0..32] of char; //关键词
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 then
begin
Result:=False;
Exit;
end;
end;
begin
{ TODO -oUser -cConsole Main : Insert code here }
i:=0;
s:='subatring searching algorithm';
p:=@s[0];//这些没用,我是测试怎么取到从数组第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.
|
|
发表于 2012-5-5 19:40:22
楼主
