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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: сочинение по английскому, реферат на
| Добавил(а) на сайт: Valentin.

Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата

Таблица смещений для образца “abbad”.

Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

Три символа образца совпали, а четвертый – нет. Сдвигаем образец вправо на одну позицию:

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 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;

Рекомендуем скачать другие рефераты по теме: шпоры по праву, реферат по физкультуре.

Claw.ru | Рефераты по информатике, программированию | Алгоритмы поиска в тексте

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

Категории:

Поделитесь этой записью или добавьте в закладки

Рефераты от А до Я

Полезные заметки