Boyer-Moore-Horspool text searching #41

function search(pat: string; text: string): integer;
var
  i, j, k, m, n: integer;
  skip: array [0..MAXCHAR] of integer;
  found: boolean;
begin
  found := FALSE;
  search := 0;
  m := length(pat);
  if m=0 then
  begin
    search := 1;
    found := TRUE;
  end;
  for k:=0 to MAXCHAR do
    skip[k] := m;   {*** Preprocessing ***}
  for k:= m-1 downto 1 do
    skip[ord(pat[k])] := m-k;
  k := m;
  n := length(text);            {*** Search ***}
  while not found and (k <= n) do
  begin
    i := k; j := m;
    while (j >= 1) do
    begin
      if text[i] <> pat[j] then
        j := -1
      else
      begin
        j := j-1;
        i := i-1;
      end;
      if j = 0 then
      begin
        search := i+1;
        found := TRUE;
      end;
      k := k + skip[ord(text[k])];
    end;
  end;
end;

Demo code

A ready made project containing this demo code is available. View the project.

This demo will use the search function provided in this tip to search a memo control for text entered in an edit control.

Create a new Delphi VCL application and proceed as follows:

Drop a TMemo on the form and set its HideSelection property to False and its ScrollBars property to ssVertical. You can also enter some text in the memo's Lines property.
Drop a TEdit and a TButton on the form.
Create an OnClick event handler for the button.
Name the form "Form1" and save the form unit as Unit1.pas.

Now code Unit1 as below:

unit Unit1;
 
interface
 
uses
  Windows, Forms, Dialogs, StdCtrls, Classes, Controls;
 
type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Edit1: TEdit;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
 
function search(pat: string; text: string): integer;
var
  i, j, k, m, n: integer;
  skip: array [0..MAXCHAR] of integer;
  found: boolean;
begin
  found := FALSE;
  search := 0;
  m := length(pat);
  if m=0 then
  begin
    search := 1;
    found := TRUE;
  end;
  for k:=0 to MAXCHAR do
    skip[k] := m;   {*** Preprocessing ***}
  for k:= m-1 downto 1 do
    skip[ord(pat[k])] := m-k;
  k := m;
  n := length(text);            {*** Search ***}
  while not found and (k <= n) do
  begin
    i := k; j := m;
    while (j >= 1) do
    begin
      if text[i] <> pat[j] then
        j := -1
      else
      begin
        j := j-1;
        i := i-1;
      end;
      if j = 0 then
      begin
        search := i+1;
        found := TRUE;
      end;
      k := k + skip[ord(text[k])];
    end;
  end;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  FoundIdx: Integer;
begin
  // search() returns 0 if the text isn't found or the index of the
  // start of the string if the text is found
  FoundIdx := search(Edit1.Text, Memo1.Text);
  if FoundIdx > 0 then
  begin
    // Found text: highlight it in memo (TMemo.HideSelection must be
    // false for this to work). Since memo selections are 0 based, we
    // subtract 1 from the found index, which is 1 based.
    Memo1.SelStart := FoundIdx - 1;
    Memo1.SelLength := Length(Edit1.Text);
  end
  else
    ShowMessage('Text not found');
end;
 
end.

Run the application. Enter some text in the memo if you didn't do this at design time. Now enter some search text in the edit control and click the button. If the text is found it will be highlighted in the memo control. A message will be displayed if the text is not found. Note that the search is case sensitive.

Demo code by Peter Johnson

Author:	Unknown
Added:	2007/06/11
Last updated:	2010/03/16