Байер Р. және Дж . Мур алгоритмі.

Байер Р. жә не Дж. Мур алгоритмі аз уақ ыттық шығ ындарды талап етеді. Жолдары іздеу s басталады, бірақ ізделініп отырғ ан ішкі жол x ү шін ө лшемі 256 (барлық мү мкін символдар саны) тең кесте қ ұ рылады. Кесте элементтері ізделініп отырғ ан ішкі соң ғ ы жол x-тен оның ә рбір символына дейінгі ара қ ашық тық (Егер x бірдей символдардан кездессе, онда кестеге ара қ ашық тық ғ ы ең жақ ыны енгізіледі). Егер x символы кірмесе, онда кестенің сә йкес ұ яшығ ына ұ зындығ ы m болатын х –ішкі жолы енгізіледі. Келесі ішкі жол индексі, келесі s символымен сә йкес келмесе, онда лайық ты ара қ ашық тық анық талады, содан кейін x лайық ты санның оң жағ ына жылжытылады. Осы арқ ылы іздеу уақ ыты қ ысқ артылады.

Мейлі s ='' МИЛА МАЛО МЫЛАСЬ МЫЛОМ', x='МЫЛО'.

х ұ зындығ ы 4-ке тең. Ара қ ашық тық кестесін қ ұ рамыз.

Ара қ ашық тық m-j символына дейін, мұ ндағ ы j - индекс, ал m - x-жолының ұ зындығ ы.

Ара қ ашық тық кестесі (sd):

Барлық кө рсетілмеген символдардың ара қ ашық тығ ы бірдей, олар 4-ке тең.

Ұ зындығ ы m ү зінділерді s жолынан белгілейміз жә не жү йелі тү рде салыстырамыз, соң ынан бастап, х символына лайық тыларын. j - нө мірі ө ң делген х жолдарының символы. s қ а лайық ты келесі символ нө мерін анық тау ү шін, s-тың қ ай позициядан бастап қ аралатынын білу керек. Ө ң делетін бө ліктің бірінші символын i арқ ылы белгілейміз. Онда s жолынан басталатын, x символының лайық ты j – нө мері, как i+j арқ ылы анық талады.

Қ адам 1. i=0, m=4. s –тің бірінші 4 символын жә не x жолын қ арастырамыз. Салыстыруды соң ынан бастаймыз, яғ ни j =4, j=4, s[i+j]< > x[j] (s[4]< > x[4]). Демек онан ә рі салыстырмауғ а да болады, себебі мынау s жол ү зіндісі, ізделіп отырғ ан ішкі жолм бола алмайды (кем дегенде бір сә йкессіздік болады). Сондық тан келесі ү зіндіге ө теміз.

Қ адам 2. Енді ү зіндінің бірінзші символының нө мірін анық тау керек. Мынаны байқ аймыз, х-те соң ғ ы фрагмент S ('А') жоқ, яғ ни келесі 2-ші, 3-ші, 4-ші фрагменттерден оны қ арамау керек, бірден 5-ші позицияғ а кө шу керек. Бұ л жағ дайда і-дің жаң а мә ні не SD ['А'] ескі мә ні қ осылады.

Сайып келгенде, s жолының жаң а ү зіндісі -' мал ' болады. Соң ынан бастап жаң а салыстыруды бастаймыз. 'Л'< > 'О' болғ андық тан бұ л бө лікті қ арастырмауғ а болады.

Қ адам 3. 'Л' символы ізделіп отырғ ан жолда бар, онда ол соң ғ ының алдындағ ысы болуы мү мкін. Демек жаң а мә н i=5 (4+sd['Л']=4+1 арқ ылы анық талады).

Анық тап қ араймыз, 'МАЛО'и 'МЫЛО': s[9]=x[4], s[8]=x[3], s[7]< > x[2] ('A'< > 'Ы'), бұ л ізделініп отырғ ан s жол ү зіндісіне келмейді.

Қ адам 4. Тө ртінші ү зінді (i=9) 'МЫЛ ''(қ адам 2 қ ара) x-ен қ айтадан сә йкес келмейді.

Қ адам 5. Келесі ү зінді i=9+sd['л']=10 -'мыло'. Бірінші салыстырудан кейін айтуғ а болады, бұ л да сә йкес келмейді.

Қ адам 6. i =14. Ү зінді ''СЬ М'' бірінші салыстырудан кейін ө ткіземіз.

Қ адам 7. i =17 (14+ sd [' m ']=14+3). Салыстыруы 'МЫЛО' жә не 'МЫЛО':

s[17+4]=x[4]

s[17+3]=x[3] => ізделінгін жол мына позициядан табылғ ан 17+1=18 (i-1).

s[17+2]=x[2]

s[17+1]=x[1]

Есеп шығ арылды.

Мақ сат шешілген.

Бұ л процесті схема тү рінде былай кө руге болады (қ алың ә ріппен сә йкес келулері белгіленген, екі рет астын сызумен –сә йкес еместері белгіленген);

МИЛА МАЛО МЫЛАСЬ МЫЛОМ

МЫЛО | 1

|МЫЛО| 2

|МЫЛО|

|МЫЛО| 3

|МЫЛО|

|МЫЛО| 4

|МЫЛО| 5

|МЫЛО| 6

|МЫЛО|

|МЫЛО| 7

|МЫЛО|

|МЫЛО|