Boyer-Mur algoritmi va xossalari

Blok-sxemalarni tuzishda foydalaniladigan asosiy sodda geometrik figuralar quyidagilardan iborat:

• 
  Algoritm uchta fikrga asoslangan:
  

  Chapdan o'ngga, o'ngdan chapga taqqoslash. Matnning boshi (qatorlar) va shablon birlashtirilib, tekshirish shablonning oxirgi belgisidan boshlanadi. Agar belgilar mos keladigan bo'lsa, shablonning oxiridan bitta oldingi simvoli va undan keyin qolganlari taqqoslanadi. Agar barcha shablon simvollari qo`shilgan simvollar satri bilan mos kelsa, naqshning barcha belgilar satrining ustki belgilariga mos keladigan bo'lsa, bunday xolda ostsatr topiladi va pastki chiziqning keyingi ko'rinishi izlanadi.

  Agar shablondagi qaysidir belgi satrda mos keladigan simvolga mos kelmasa, shablon bir nechta belgi o'ngga siljiydi va test oxirgi belgidan yana boshlanadi.

  Stop simvollar: Keling, "kolokol" so'zini izlaylik. Birinchi harfga mos kelmadi - "k" (ushbu harfni to'xtash belgisi deb nomlaylik). So'ng shablonni o'ngdan oxirigacha "k" harfi bilan surishingiz mumkin.

Строка: * * * * * * к * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Shablonda da hech qanday to'xtash belgisi bo'lmasa, shablon bu to'xtash belgisidan tashqariga o'tadi.

Строка: * * * * * а л * * * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л

 

Bunday holatda, stop simvoli "a" hisoblanadi. Shablon esa to`g`ridan to`g`ri bu harfni ko`rsatgani uchun siljiydi. Boyer-Moor algoritmida stop simvoli mos keladigan qo'shimchaga umuman qaramaydi, Shuning uchun shablonning birinchi harfi ("k") "l" ostida bo'ladi va ma'lum bo'lgan bo'shliq bajariladi. Agar to'xtash belgisi "k" boshqa harfdan keyin "k" bo'lsa, stop simvoli ishlamaydi.

Строка: * * * * к к о л * * * * *Шаблон: к о л о к о л

Следующий шаг: к о л о к о л ?????

• 
  Ushbu algoritmni C++ da amlaga oshirish quyidagicha:
  

Boyer-Mur algoritmining 1-modifikasiyasi. BM algoritmida foydalaniladigan yomon simvol siljishi kichik bo’lgan alifbo uchun uncha samarali emas, lekin alifbo o’rtasi namuna uzunligiga qaraganda katta bo’lsa, bu ASCII jadvali bilan bo’lgan holda va matn muharririda oddiy izlashda, u juda foydali. Algoritmda faqat uning bittasidan foydalanish juda samarali bo’ladi.