Зертханалық жұмыс

жүктеу 1,28 Mb.

бет	34/38
Дата	23.01.2020
өлшемі	1,28 Mb.
	#27192

1 ... 30 31 32 33 34 35 36 37 38

Мысалы

массивін қалай толтыру керек?

Шешімі
барлық pos[s]қойыңыз б тең 0 болғандай

for i:=1 to n do begin
pos[x[i]]:=i;
end;

Іздеу үдерісінде біз

ауысымын сөздегі әріпті сақтаймыз, үлгінің соңғы әрпі тұрғанға қарсы.

басында (үлгі ұзындығы), ал сосын біртіндеп өседі.

last:=n;
{Қалған барлық үлгі жағдайлары тексерілген}

while last <= m do begin {сөз аяқталған жоқ}
| if x[m] <> y[last] then begin {соңғы әріптері әр түрлі}
| | last := last + (n - pos[y[last]]);
| | {n - pos[y[last]] – бұл үлгінің минималды түрде жылжығаны,
| | керісінше y[last] сол қалыпында қалады
| | үлгідегі әріп. Егер сондай әріп болмаса,
| | онда үлгінің барлық ұзындығын жылжытамыз}
| end else begin
| | егерде кейінгі жағдайы келіп тұрса,
| | x[1]..x[n] = y[last-n+1]..y[last],
| | онда сәйкестікті хабарланыз;
| | last := last+1;
| end;
end;
Білгіштер сәйкестікті оңнан солға қарай өткізуді ұсынып отыр. Яғни үлгінің соңғы әрпінен бастау керек (онда сәйкестіктер болу керек).

Бұл алгоритмнің әр түрлі модификациясы болуы мүмкін.

Мысалы,

жолын

жолына ауыстыруға болады, онда

– координаттары

екінші оң жағындағы шығу әріптері.

Осыны бағдарламада қалай ескеруге болады?

Шешімі.

кестесін құрғанда

for i:=1 to n-1 do... жазыңыз (ары қарай бұрыңғыша), ал негізгі бағдарламада

орнына

жазыңыз;

Келтірілген Бойер - Мура алгоритмнің жеңіл түрі кей жағдайда n әрекетін көбірек талап етеді. (

сандар әрекетінің тәртібі), Кнута - Моррис – Пратта алгоритмінен кішкене ғана жеңіліп қалдық.

жүктеу 1,28 Mb.

Достарыңызбен бөлісу:

1 ... 30 31 32 33 34 35 36 37 38