Va innovatsiyalar vazirligi osiyo xalqaro universitetining ijtimoiy

Oldindan ishlov berish
Yaxshi qo'shimchalar qoidasi ikkita jadvalni talab qiladi: biri umumiy holatda foydalanish uchun (t' nusxasi topilgan joyda), ikkinchisi esa umumiy holat mazmunli natija bermaganda foydalanish uchun. Ushbu jadvallar mos ravishda L va H bilan belgilanadi.
Ularning ta'riflari quyidagicha:
Har bir i uchun L[i] m dan kichik boʻlgan eng katta pozitsiya boʻlib, P[i..m]} qatori P[1..L[i]] qoʻshimchasiga mos keladi va bu qoʻshimchadan oldingi belgi boʻlmaydi. P[i-1] ga teng.
Agar shartni qondiradigan pozitsiya bo'lmasa, L [i] nolga teng deb hisoblanadi.
H[i] ning eng katta qo‘shimchasining uzunligini bildirsin
P[i..m]}, agar mavjud bo'lsa, bu ham P ning prefiksidir. Agar yo'q bo'lsa, ruxsat bering
H[i] nol bo'lsin.
Ushbu jadvallarning ikkalasi ham O(m) vaqt ichida tuzilishi mumkin va O(m) fazodan foydalanadi. Pdagi i indeksi uchun hizalanish siljishi m bilan berilgan
L[i]} yoki m-H[i]}. H faqat L[i] nolga teng bo'lsa yoki moslik topilsa ishlatilishi kerak.
Galil hukmronligi
Boyer-Murning oddiy, ammo muhim optimallashtirish 1979 yilda Zvi Galil tomonidan ilgari surilgan. O'zgartirishdan farqli o'laroq, Galil qoidasi mos kelishi ma'lum bo'lgan qismlarni o'tkazib yuborish orqali har bir tekislashda amalga oshirilgan haqiqiy taqqoslashlarni tezlashtirish bilan shug'ullanadi. Faraz qilaylik, k1 tekislashda P T bilan T ning c belgisigacha taqqoslanadi. Keyin agar P k2 ga uning chap uchi c va k1 o'rtasida bo'ladigan tarzda o'tkazilsa, keyingi taqqoslash bosqichida P prefiksi pastki qatorga mos kelishi kerak. T(k2 - n)..k1. Shunday qilib, agar taqqoslashlar T ning k1 pozitsiyasiga tushsa, o'tgan k1 ni aniq taqqoslamasdan P ning paydo bo'lishini qayd etish mumkin. Boyer-Murning samaradorligini oshirishdan tashqari, Galil qoidasi eng yomon holatda chiziqli vaqtning bajarilishini isbotlash uchun talab qilinadi.
Galil qoidasi, asl nusxasida, faqat bir nechta mos keladigan versiyalar uchun samarali. U substring diapazonini faqat c = 0 da yangilaydi, ya'ni to'liq mos keladi. Submatchlar bilan ishlashning umumlashtirilgan versiyasi 1985 yilda Apostoliko-Giankarlo algoritmi sifatida e'lon qilingan.
Ishlash
Dastlabki maqolada keltirilgan Boyer-Mur algoritmi eng yomon ish vaqtiga ega O(n+m) faqat matnda naqsh ko‘rinmasa. Buni birinchi marta 1977 yilda Knut, Morris va Pratt isbotlagan, keyin esa 1980 yilda Guibas va Odlizko eng yomon holatda 5n yuqori chegarasi bilan taqqoslagan. Richard Koul 1991-yilda eng yomon holatda 3n taqqoslashning yuqori chegarasi bilan dalil keltirdi.
Agar naqsh matnda paydo bo'lsa, eng yomon holatda asl algoritmning ishlash vaqti O (nm) dir. Naqsh va matn faqat bir xil takrorlanuvchi belgidan iborat bo'lganda buni ko'rish oson. Biroq, Galil qoidasining kiritilishi barcha holatlarda chiziqli ish vaqtiga olib keladi.
Amalga oshirish
Turli xil dasturlash tillarida turli xil ilovalar mavjud. C++ tilida u C++ 17 dan beri standart kutubxonaning bir qismidir, shuningdek Boost algoritm kutubxonasi ostida umumiy Boyer-Mur qidiruv dasturini taqdim etadi. Go (dasturlash tili) da search.go ilovasi mavjud. D (dasturlash tili) Phobos Runtime Library-ning bir qismi sifatida diapazonlarda predikatlar asosidagi moslashish uchun Boyer Moore Finderdan foydalanadi.
Boyer-Mur algoritmi GNU grepida ham qo'llaniladi.