Информатика, программирование / Реферат: Алгоритмы поиска в тексте

Реферат: Алгоритмы поиска в тексте

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:

Еще раз сдвигаем образец на 2 позиции:

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

Реализуем указанный алгоритм на языке ObjectPascal. Прежде всего следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение этого типа будет выглядеть так:

type

TBMTable = array [0..255] of Integer;

Далее приводится процедура, вычисляющая таблицу смещений для образца P.

procedure MakeBMTable( var BMT : TBMTable; const P : String);

var

i : Integer;

begin

for i := 0 to 255 do BMT[i] := Length(P);

for i := Length(P) downto 1 do

if BMT[Byte(P[i])] = Length(P) then

BMT[Byte(P[i])] := Length(P) – i;

end;

Теперь напишем функцию, осуществляющую поиск.

function BMSearch( StartPos : Integer; const S, P : String;

const BMT : TBMTable) : Integer;

var

Pos, lp, i : Integer;

begin

lp := Length(P);

Pos := StartPos + lp –1;

while Pos < Length(S) do

if P[lp] <> S[Pos] then Pos := Pos + BMT[S[Pos]]

К-во Просмотров: 328

Бесплатно скачать Реферат: Алгоритмы поиска в тексте

>>> Скачать <<<