Matn içida qidiruv. Boyer-Moore algoritmi

Avvalgi mavzuda ötganimiz - Knuth-Morris-Pratt algoritmi yordamida biz matn içida qidiruvni O(N + M) vaqt içida bajara olamiz. Navbatdagi algoritm - Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq işlaydi. Örganişga ham osonroq ;)
Boyer-Moore'ning taklifiga köra:
- pattern'dagi belgilarni öngdan çapga (pattern ohiridan boşiga) qarab körib çiqiş;
- pattern'da yöq bölgan belgi topilganda maksimum M miqdordagi belgilarni tekşirmay taşlab ketiş. Bu yerda M - pattern'dagi belgilar soni
Bizda quyidagi matn bor bölsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE
qidiruvni pattern'ning ohirgi harfidan boşlaymiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
Dastlabki tekşirilayotgan belgi - E matnning dastlabki M-elementiga teng emas (N != E). Ammo N pattern içida bor. Keyingi tekşiriş uçun pointerni N qilib belgilaymiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
S != E, şu bilan birga S pattern içida yöq. Demak bizga S va undan oldingi belgilarning qiziği yöq. Keyingi tekşiriş uçun pointerni S dan keyingi elementga beramiz (bu yerda -T).
FINDINAHAYSTACKNEEDLEINA NEEDLE
E == E lekin keyingi element N != L. Patternda N bor. Keyingi tekşiriş uçun pointerni mana şu Nga beramiz.
FINDINAHAYSTACKNEEDLEINA NEEDLE
Pattern matn içidan topildi.
Misoldagi tuşirib qoldirişlar turini tahlil qiladigan bölsak, bizda pattern'dagi belgining mos kelmasligi böyiça (character mismatç) bir neça holatlar mavjud.
1. Mos kelmagan belgi pattern içida yöq. Bu holda pointer mos kelmagan belgidan keyinga qö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 içida bor.
matn: ......NLE...... patt: NEEDLE
Bu holda agar belgi pattern'ning birinçi belgisi bölsa, pointer şu belgiga qöyiladi.
matn: ......NLE...... patt: NEEDLE
2b. Mos kelmagan belgi pattern içida bor, lekin u patternning birinçi elementiga mos kelmaydi.
matn: ......ELE...... patt: NEEDLE
matn: ......ELE...... patt: NEEDLE
Biz E pattern'dagi qaysi Ega mos kelişini bilmaymiz. Şuning uçun pointerni bittaga oşiramiz xolos.
Umuman, algoritmdagi eng muhim jihat - qança belgini tekşirmasdan taşlab ketişni aniqlab oliş kerak böladi. Buning uçun pattern'dagi belgilar asosida ikki ölçamli array yasab olinadi. Unda alfavitdagi har bir harfning pattern'dagi örni belgilanadi.
-1 - pattern'da yö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 |
Boyer-Moore'ning tuşirib qoldirişni hisoblaş jadvali
Biz bu jadvalni kodga ögiradigan bölsak:
Töliq kod
Algoritmning işlaş vaqti ~ O(N/M) ga teng. Bu degani pattern qança uzun bölsa, algoritmning işlaş vaqti qisqarib boraveradi.
Worst case. Şuni ham qayd etiş kerakki, işlaş vaqti ba'zi holatlarda O(N*M) bölib ketişi mumkin:
BBBBBBBBBB ABBBB ABBBB ABBBB ABBBB ABBBB ABBBB
Masalan, yuqoridagi holatda işlaş vaqti O((N-M) * M) ga teng.