Avvalgi mavzuda o’tganimiz – Knuth-Morris-Pratt algoritmi yordamida biz matn ichida qidiruvni O(N + M) vaqt ichida bajara olamiz. Navbatdagi algoritm – Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq ishlaydi. O’rganishga ham osonroq 😉
Boyer-Moore’ning taklifiga ko’ra:
- pattern’dagi belgilarni o’ngdan chapga (pattern ohiridan boshiga) qarab ko’rib chiqish;
- pattern’da yo’q bo’lgan belgi topilganda maksimum M miqdordagi belgilarni tekshirmay tashlab ketish. Bu yerda M – pattern’dagi belgilar soni
Bizda quyidagi matn bor bo’lsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE
qidiruvni pattern’ning ohirgi harfidan boshlaymiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
Dastlabki tekshirilayotgan belgi – E matnning dastlabki M-elementiga teng emas (N != E). Ammo N pattern ichida bor. Keyingi tekshirish uchun pointerni N qilib belgilaymiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
S != E, shu bilan birga S pattern ichida yo’q. Demak bizga S va undan oldingi belgilarning qizig’i yo’q. Keyingi tekshirish uchun pointerni S dan keyingi elementga beramiz (bu yerda -T).
FINDINAHAYSTACKNEEDLEINA NEEDLE
E == E lekin keyingi element N != L. Patternda N bor. Keyingi tekshirish uchun pointerni mana shu Nga beramiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
Pattern matn ichidan topildi.
Misoldagi tushirib qoldirishlar turini tahlil qiladigan bo’lsak, bizda pattern’dagi belgining mos kelmasligi bo’yicha (character mismatch) bir necha holatlar mavjud.
1. Mos kelmagan belgi pattern ichida yo’q. Bu holda pointer mos kelmagan belgidan keyinga qo’yiladi. Masalan
matn: ......TLE...... patt: NEEDLE
D != T, pointer T dan keyingi element – L ga beriladi.
matn: .......TLE...... patt: NEEDLE
2a. Mos kelmagan belgi pattern ichida bor.
matn: ......NLE...... patt: NEEDLE
Bu holda agar belgi pattern’ning birinchi belgisi bo’lsa, pointer shu belgiga qo’yiladi.
matn: ......NLE...... patt: NEEDLE
2b. Mos kelmagan belgi pattern ichida bor, lekin u patternning birinchi elementiga mos kelmaydi.
matn: ......ELE...... patt: NEEDLE
matn: ......ELE...... patt: NEEDLE
Biz E pattern’dagi qaysi Ega mos kelishini bilmaymiz. Shuning uchun pointerni bittaga oshiramiz xolos.
Umuman, algoritmdagi eng muhim jihat – qancha belgini tekshirmasdan tashlab ketishni aniqlab olish kerak bo’ladi. Buning uchun pattern’dagi belgilar asosida ikki o’lchamli array yasab olinadi. Unda alfavitdagi har bir harfning pattern’dagi o’rni belgilanadi.
-1 – pattern’da yo’q degani.
| N | E | E | D | L | E | |||
| c | 0 | 1 | 2 | 3 | 4 | 5 | right[c] | |
| A | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| B | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| C | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| D | -1 | -1 | -1 | -1 | 3 | 3 | 3 | 3 |
| E | -1 | -1 | 1 | 2 | 2 | 2 | 5 | 5 |
| … | -1 | |||||||
| L | -1 | -1 | -1 | -1 | -1 | 4 | 4 | 4 |
| M | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| N | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | -1 |
Biz bu jadvalni kodga o’giradigan bo’lsak:
To’liq kod
Algoritmning ishlash vaqti ~ O(N/M) ga teng. Bu degani pattern qancha uzun bo’lsa, algoritmning ishlash vaqti qisqarib boraveradi.
Worst case. Shuni ham qayd etish kerakki, ishlash vaqti ba’zi holatlarda O(N*M) bo’lib ketishi mumkin:
BBBBBBBBBB ABBBB ABBBB ABBBB ABBBB ABBBB ABBBB
Masalan, yuqoridagi holatda ishlash vaqti O((N-M) * M) ga teng.