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

жүктеу 1,28 Mb.

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

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

Тапсырма 1

Жағдай мысалын келтіріңіз, оның ішіндегі үлгі сөзге кірмейді, бірақта оны белгілеу үшін, алгоритм

әрекетіндегі тәртіпті талап етеді.

Нақты (жеңілдетілмеген) Бойера - Мура алгоритмі кепілденеді, әрекеттер саны

аспайды. Ол Кнут-Моррис-Пратта алгоритмінің идеяларына жақын, идеялар пайдаланады. Оңнан солға жүргенде біз кірген сөзбен үлгіні салыстырайық. Кейбір

бөлігі (үлгінің соңы болып келген) тең келді, ал сосын айырмашылығын таптық: үлгіде

алдында кіру сөзіндегідей емес болып келеді.Бұл кезде кіру сөзі туралы не айтуға болады? Оның ішінде

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

үлгінің әр соңы үшін алдан ала есептеп алған жөн. Ғалымдардың айтуынша, бұнын барлығы (жылжудың кестесін және оның қолдануын есептеу)

әрекетіне қоюға болады.

жүктеу 1,28 Mb.

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

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