Поиск подстроки

Begin

Begin

Var

Ввод значения строк в стандарте языка Pascal

Операции над строками

Var

Type

Строки.

Нетипизированные параметры

Параметры - константы

Begin

Var

Begin

Begin

Var

a, b: integer;

procedure add1(x: integer; var y: real);

x:=x + 1;

y:=y + 1;

writeln(‘x=’,x,’y=’,y);

end;

a:=0;

b:=0;

add1(a,b);

writeln(‘a=’,a,’b=’b);

end;

x=1	y=1
a=0	b=1

Параметры - процедуры (параметры – функции)

procedure p1(procedure ff; function a:real);

Пример. Табулирование функции

Procedure tab(lower, upper, step:real; function f(x:real):real);

x:real;

x:=lower;

while x < = upper do begin

write(x:10,’ ‘,f(x):10);

x:=x + step;

end;

end;

Перед параметром записывается слово const. В этом случае передается ссылка (адрес) на область памяти, где располагается фактический параметр. Компилятор блокирует присваивании. Используется для работы с большими массивами.

Записываются аналогично параметрам – переменным, но без типа. Фактические параметры при этом безтиповые указатели. Используется для работы с большими массивами.

ЛЕКЦИЯ №13

Строка – конечная последовательность символов, которую можно рассматривать как особую форму одномерного массива.

Различают строковые константы и строковые переменные.

Пример объявления строковой переменной

<строковый тип>::=packed array [1..N] of char

N>1, т.к. не существует строк без литер или с одной литерой.

stroka=packed array[1..27] of char;

str1:stroka;

str2:packed array[1..27] of char;

q:boolean;

1. Все операции над массивами действительны для строк.

2. Имеются специальные операции над строками

А) инициализация строк

str1:=’мы изучаем стандарт Паскаль’; 27 символов

str2:=’turbo pascal ‘; 27 символов

Б) строковые переменные одинаковой длины можно сравнивать
(=, <>, <, >, <=, >=).

q:=str1 = str2 {false};

q:=str1 < str2 {false};

q:=str 1 > str2 {true};

Задача. Составить список подарков для детей.

program presents;

const n = 30;

shablon=’ ‘;

type nametoy=packed array [1..6] of char;

spisok=array[1..n] of nametoy;

podarki:spisok;

name:nametoy;

sym:char;

i,j:integer;

for i:=1 to n do begin

name:=shablon;{для инициализации строк применяем шаблон}

j:=1;

read(sym);

{посимвольно вводим строку}

While (sym<>’,’) and (sym <>’.’) do

name[j]:=sym;

j:=j+1;

read(sym);

end;

(string matching)

Дан текст и образец T[1..n] и P[1..m], m<=n;

P входит со сдвигом S в текст T, если 0<=S<=n-m

T[s+1..s+m]=P[1..m];

Задача поиска подстроки заключается в нахождении всех допустимых
сдвигов для Т и Р.

Пусть требуется найти вхождение P=’aaab’ в текст T=’abcaaabbc’. Образец входит в образец со сдвигом 3.

a	b	c	a	a	a	b	b	c
S=3	a	a	a	b

Простейший алгоритм поиска подстроки:

Последовательно проверять равенство Т[s+1..s+m]=P[1..m] для каждого из n-m+1 возможных значений

…{ сравнение слева направо }

For s=0 ti n-m do begin

j:=0;

while (j <= m) and (p[j] = t[s + j]) do j:=j + 1;

if j=m + 1 then writeln(‘ Образец входит со сдвигом ‘, s);

end;

Во внешнем цикле мы сдвигаем образец вдоль текста на S позиций, а во внутреннем проверяем равенство символов образца и текста, начиная с позиции S+1. Если внутренний цикл завершится при j=m+1, то образец входит в текст со сдвигом S.

В обратном порядке

…

{ сравнение справа налево с использованием while }

S:=0;

While S < = (n – m) do begin

j:=m;

while (j > 0) and (p[j]=t[s+j]) do j:=j + 1;

if j = 0 then writeln(‘ Входит со сдвигом’, S);

S:=S + 1;

end;

Время работы пропорционально произведению (n – m + 1) * m. Это не лучший алгоритм.

Неэффективность простейшего алгоритма связана с тем, что информация при проверке вхождения при очередном сдвиге S никак не используется при проверке следующего сдвига.

P = ’aaab’ Если сдвиг S = 0 допустим, то сдвиги 1, 2,3 заведомо недопустимы.

Алгоритм Бойера – Мура

Этот алгоритм использует для усовершенствования эвристику «стоп-символа», эвристику «безопасного суффикса». Они позволяют не рассматривать некоторые значения сдвига S.

Если при проверке вхождения Р в Т обнаруживается несовпадение символов, то каждая из эвристик указывает значение на которое можно увеличить s, не опасаясь пропустить допустимый сдвиг. Выбирается больший из сдвигов.

…

w

r

i

t

t

e

n

_

n

o

t

i

c

e

_

t

h

a

t

_

s

r

e

m

i

n

i

s

c

e

n

c

e

Эвристика стоп – символа

…

w

r

i

t

t

e

n

_

n

o

t

i

c

e

_

t

h

a

t

_

S+4

r

e

m

i

n

i

s

c

e

n

c

e

Эвристика безопасного суффикса

…

w

r

i

t

t

e

n

_

n

o

t

i

c

e

_

t

h

a

t

_

S+3

r

e

m

i

n

i

s

c

e

n

c

e

Упрощенный вариант алгоритма БМ.

{ алгоритм Бойера-Мура с использованием стоп-символа }

S:=0;

while s < = (n – m) do begin

j:=m

while (j > 0) and (p[j]=t[s+j])

if j = 0 then begin

writeln(‘ Входит со сдвигом’, S);

S:=S + 1;

Дата добавления: 2014-01-07