经过多年研究,本人已经设计一种高效率的字符串查找算法,比绝大部分的查找算法快5-10倍,教科书上经典的KMP算法
实在太慢,太复杂,难以理解,本人设计的算法,简单,快速,现在贴上代码,请各位测试验证。该算法暂时命名为TRH算法。其设计思想暂时不公布,先请大家验证该程序,看看效率到底怎么样?依照本人的测测试,比DELPHI POS函数快8倍左右!本算法特别对于待查找的子字符串比较长时候(>=100)优势极为明显!下面为算法过程的程序:{
函数参数说明:
StrArr:文本字符串,其类型为一个自定义字符数组 TYPE TARR = array[1..NSIZE] of char;
SubStr:待查找的子字符串
loc:返回所有出现子字符串的位置 }
procedure TRH_STR_SEARCH(const StrArr: TARR; SubStr:string; var Loc: string);
var
I, J, K: integer;
StrLen, SubStrLen: integer;
FindTable: array[0..255] of integer;
SKIP: integer;
begin
SubStrLen := Length(SubStr);
StrLen := Length(StrArr); for i := 0 to 255 do
begin
FindTable[i] := SubStrLen + 1;
end; for i := 1 to SubStrLen do
begin
FindTable[ord(SubStr[i])] := SubStrLen - i + 1;
end; I := 1;
while I <= StrLen - SubStrLen + 1 do
begin
K := I ;
for J := 1 to SubStrLen do
if StrArr[K] = SubStr[J] then
inc(K)
else
break; if K - I = SubStrLen then
begin
Loc := Loc +IntToStr(I)+ ' , ';
inc(I, SubStrLen);
end else
begin
SKIP := FindTable[ord(StrArr[I + SubStrLen])];
inc(I, SKIP);
end;
end;
end;调用方法:
在公共部分先声明和定义数组和变量const
NSIZE = 50000000 ;type
TARR = ARRAY[1..NSIZE] OF CHAR; var
strarr : TARR; //当NSIZE很大时候,TARR要为全局变量,如果为局部变量,可能会出错。implementation{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
loc:string;
substr:string;
i:integer;
stime,etime:cardinal;
begin
//用随机函数初始化数组。
randomize;
for i := 1 to nsize do
begin
strarr[i]:=chr(65+random(26));
end; substr := copy(strarr,random(nsize),100);//截取任意段字符串,作为待查的子字符串;
stime := gettickcount ; TRH_STR_SEARCH(STRARR,SUBSTR,LOC); etime := gettickcount; listbox1.Items.Add('time is : '+ inttostr(etime - stime));
listbox1.Items.Add(substr+' loc is : ' + loc);end;
实在太慢,太复杂,难以理解,本人设计的算法,简单,快速,现在贴上代码,请各位测试验证。该算法暂时命名为TRH算法。其设计思想暂时不公布,先请大家验证该程序,看看效率到底怎么样?依照本人的测测试,比DELPHI POS函数快8倍左右!本算法特别对于待查找的子字符串比较长时候(>=100)优势极为明显!下面为算法过程的程序:{
函数参数说明:
StrArr:文本字符串,其类型为一个自定义字符数组 TYPE TARR = array[1..NSIZE] of char;
SubStr:待查找的子字符串
loc:返回所有出现子字符串的位置 }
procedure TRH_STR_SEARCH(const StrArr: TARR; SubStr:string; var Loc: string);
var
I, J, K: integer;
StrLen, SubStrLen: integer;
FindTable: array[0..255] of integer;
SKIP: integer;
begin
SubStrLen := Length(SubStr);
StrLen := Length(StrArr); for i := 0 to 255 do
begin
FindTable[i] := SubStrLen + 1;
end; for i := 1 to SubStrLen do
begin
FindTable[ord(SubStr[i])] := SubStrLen - i + 1;
end; I := 1;
while I <= StrLen - SubStrLen + 1 do
begin
K := I ;
for J := 1 to SubStrLen do
if StrArr[K] = SubStr[J] then
inc(K)
else
break; if K - I = SubStrLen then
begin
Loc := Loc +IntToStr(I)+ ' , ';
inc(I, SubStrLen);
end else
begin
SKIP := FindTable[ord(StrArr[I + SubStrLen])];
inc(I, SKIP);
end;
end;
end;调用方法:
在公共部分先声明和定义数组和变量const
NSIZE = 50000000 ;type
TARR = ARRAY[1..NSIZE] OF CHAR; var
strarr : TARR; //当NSIZE很大时候,TARR要为全局变量,如果为局部变量,可能会出错。implementation{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
loc:string;
substr:string;
i:integer;
stime,etime:cardinal;
begin
//用随机函数初始化数组。
randomize;
for i := 1 to nsize do
begin
strarr[i]:=chr(65+random(26));
end; substr := copy(strarr,random(nsize),100);//截取任意段字符串,作为待查的子字符串;
stime := gettickcount ; TRH_STR_SEARCH(STRARR,SUBSTR,LOC); etime := gettickcount; listbox1.Items.Add('time is : '+ inttostr(etime - stime));
listbox1.Items.Add(substr+' loc is : ' + loc);end;
kmp本来就是中看不中用的花架子,任何一本算法书都会提到它没实用价值