Title: Position of a string in another string (fast)
Question: You need to find a string within another, and this should be done very fast...
Answer:
The FastPos routine searches for a string within a sub string using a faster algorithm than the standard Delphi Pos does.
It first builds a table with the last occurence of each character in the string to be found. Then it looks up the current character in the string to be searched. If the character matches the last character of the string to be found, it will look for a match. If it doesn't match, or the character is different it will look up the difference between the current character and the last character in the string to be found and increment the search position accordingly.
The following routine is used the same way the Delphi routine POS is used.
function FastPos(const InStr, SearchStr: String): LongInt;
var
Current, LastCharacter: Char;
ASCII: array[0..255] of LongInt;
I, J, K, LenInStr, LenSearchStr: LongInt;
begin
Result := 0;
// get length of strings
LenInStr := Length(InStr);
LenSearchStr := Length(SearchStr);
for I := 0 to 255 do
ASCII[I] := LenInStr;
// fill jump table according to last occurence of each character
for I := 1 to LenInStr - 1 do
ASCII[Ord(InStr[I])] := LenInStr - I;
// get last character of InStr
LastCharacter := InStr[LenInStr];
// find start position
I := LenInStr;
// loop through search string
while I begin
// get current character
Current := SearchStr[I];
// compare current character with last character of InStr
if Current = LastCharacter then
begin
// compare strings
J := I - LenInStr;
K := 1;
while K begin
// compare string found at current position
if InStr[K] SearchStr[J + K] then
Break;
Inc(K);
end;
// K equal the length of the string to be found
if K = LenInStr then
begin
// return position of string
Result := J + 1;
// quit
Exit;
end;
// jump to next possible position
Inc(I, ASCII[Ord(Current)]);
end else begin
// jump to next possible position of last character
Inc(I, ASCII[Ord(Current)]);
end;
end;
end;