Va innovatsiyalar vazirligi osiyo xalqaro universitetining ijtimoiy

Ta'riflar
T - qidiruv uchun kiritiladigan matnni bildiradi. Uning uzunligi n.
P - izlanadigan satrni bildiradi, naqsh deb ataladi. Uning uzunligi m.
S[i] - 1 dan boshlab S qatorning i indeksidagi belgini bildiradi.
S[i..j] - i indeksdan boshlanib, j bilan tugaydigan S qatorning pastki qatorini bildiradi.
S ning prefiksi [1, l] diapazonidagi ba'zi i uchun S[1..i] pastki qatordir, bu yerda
l - S ning uzunligi.
S ning qoʻshimchasi [1, l] diapazonidagi baʼzi i uchun S[i..l] qator qatori boʻlib,
bu yerda l — S ning uzunligi.
P ning T ga tekislanishi T dagi k indeks bo‘lib, P ning oxirgi belgisi T ning
k indeksiga to‘g‘ri keladi.

A	N	P	A	N	M	A	N	-
P	A	N	-	-	-	-	-	-
-	P	A	N	-	-	-	-	-
-	-	P	A	N	-	-	-	-
-	-	-	P	A	N	-	-	-
-	-	-	-	P	A	N	-	-
-	-	-	-	-	P	A	N

Agar P T[(k-m+1)..k] ga ekvivalent bo'lsa, k tekislashda P mos kelishi yoki paydo bo'lishi sodir bo'ladi


Tavsif
Boyer-Mur algoritmi turli xil tekislashlarda aniq belgilar solishtirishni amalga oshirish orqali Tda P ning paydo bo'lishini qidiradi. Barcha hizalamalarni qo'pol kuch bilan qidirish o'rniga (ular mavjud n-m+1}), Boyer-Mur imkon qadar ko'proq tekislashni o'tkazib yuborish uchun P ga oldindan ishlov berish orqali olingan ma'lumotlardan foydalanadi.
Ushbu algoritmni joriy etishdan oldin, matn ichida qidirishning odatiy usuli matnning har bir belgisini naqshning birinchi belgisi uchun tekshirish edi. Bu topilgandan so'ng, matnning keyingi belgilari naqsh belgilari bilan taqqoslanadi. Agar mos kelmasa, matn yana belgilar bo'yicha tekshiriladi va moslikni topishga harakat qilinadi. Shunday qilib, matndagi deyarli har bir belgi tekshirilishi kerak.
Ushbu algoritmdagi asosiy tushuncha shundan iboratki, agar naqshning oxiri matn bilan taqqoslansa, matnning har bir belgisini tekshirish o'rniga matn bo'ylab sakrashlar amalga oshirilishi mumkin. Bu ishning sababi, naqshni matnga qarama-qarshi qo'yishda naqshning oxirgi belgisi matndagi belgi bilan taqqoslanadi. Agar belgilar mos kelmasa, matn bo'ylab orqaga qarab qidirishni davom ettirishning hojati yo'q. Agar matndagi belgi naqshdagi belgilarning birortasiga mos kelmasa, u holda tekshiriladigan matndagi keyingi belgi matn bo‘ylab m belgi uzoqroqda joylashgan bo‘ladi, bu erda m - naqsh uzunligi. Agar matndagi belgi naqshda bo'lsa, u holda matn bo'ylab naqshning qisman siljishi mos keladigan belgi bo'ylab tekislanadi va jarayon takrorlanadi. Matndagi har bir belgini tekshirish o'rniga taqqoslash uchun matn bo'ylab sakrab o'tish, taqqoslashlar sonini kamaytiradi, bu esa algoritm samaradorligining kalitidir.
Rasmiyroq qilib aytganda, algoritm k=m tekislashdan boshlanadi, shuning uchun P ning boshlanishi T ning boshlanishi bilan tekislanadi. Keyin P va T dagi belgilar m indeksidan P va T da k indeksidan boshlab, orqaga qarab solishtiriladi. Satrlar P ning oxiridan P ning boshigacha moslashtiriladi. Taqqoslash P ning boshiga yetguncha (bu mos kelma borligini bildiradi) yoki mos kelmaslik yuzaga kelguncha davom etadi, natijada hizalanish oldinga (o‘ngga) siljiydi. bir qator qoidalar tomonidan ruxsat etilgan maksimal qiymatga muvofiq. Taqqoslashlar yangi tekislashda yana amalga oshiriladi va jarayon T ning oxiridan o'tib ketmaguncha takrorlanadi, ya'ni boshqa mosliklar topilmaydi.
Shift qoidalari P.ni oldindan qayta ishlash jarayonida yaratilgan jadvallar yordamida doimiy vaqt jadvallarini qidirish sifatida amalga oshiriladi.