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

жүктеу 1,28 Mb.

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

1 2 3 4 5 6 7 8 9 ... 38

Мысалы

кестені толтыру алгоритмін жазыңыз.

Шешімі. I бірінші мағынасы

табылған деп есептейі. Біз сөздін кезекті әріпін оқимыз (т.е.

) және есептеуміз керек

--------------------------------------------------------

| x | | оқылған бөлігі
--------------------------------------------------------
\-----------Z-----------/ \------------Z------------/
Басқа сөзбен айтқанда,

сөзінің бас жағы бізге керегі

, Оны соңы болып табылады – оның ішінен ең ұзының таңдауымыз керек. Бұл басталымдыр қайдан алынған. Әр қайсысы (босты санамағанда )

кейбір сөзінен

әріптерін қосқанда. пайда болады.

сөзі

сөздін басы және аяқ жағы болып келеді. Бірақта

сөздің басы мен аяғы болып келетін сөздер келе бермейді, одан кейін

әріпі тұру керек.

сөзін табу жолы пайда болады. Алдымен

барлық сөздердің басын қарастырайық, сол уақытта ол олардың аяқ жағы болып табылады. Олардың ішінен

әріпінен кейін тұратын сөзді таңдайық. Қажеттінің ішінен ең ұзының таңдайық. Ең соңына

жазғанда,

ізделетін сөзді аламыз.
Енді айтқандардың бәрін төменде қарастырайық.

i:=1; l[1]:= 0;

{кесте l[1]..l[i] дұрыс толтырылған}
while i <> n do begin
| len := l[i]
| {len – сөз басының ұзындығы x[1]..x[i], оның соңы болып келетін
| ең ұзын басталымдар қажет болмай қалды
| }
| while (x[len+1] <> x[i+1]) and (len > 0) do begin
| | {бас жағы келмейді, l функциясын қолданайық}
| | len := l[len];
| end;
| {керектіні таптыңыз ба немесе жоқ екеніне көзіңіз жетті ме? }
| if x[len+1] = x[i+1] do begin
| | {x[1]..x[len] - ең қажетті ұзын бас жағы}
| | l[i+1] := len+1;
| end else begin
| | {қажеттілері жоқ}
| | l[i+1] := 0;
| end;
| i := i+1;
end;

жүктеу 1,28 Mb.

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

1 2 3 4 5 6 7 8 9 ... 38