Mavzu : matnda qidiruv algoritimini tahlil qilish

1. Mos kelmagan belgi pattern ichida yo’q. Bu holda pointer mos kelmagan belgidan keyinga qo’yiladi. Masalan

D != T, pointer T dan keyingi element – L ga beriladi.


2a. Mos kelmagan belgi pattern ichida bor.

Bu holda agar belgi pattern’ning birinchi belgisi bo’lsa, pointer shu belgiga qo’yiladi.

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.


Boyer-Moore’ning tushirib qoldirishni hisoblash jadvali
Biz bu jadvalni kodga o’giradigan bo’lsak:

To’liq kod:

JavaScript:

To’liq kod:

Php:

function BoyerMoore($text, $pattern)

{
$patlen = strlen($pattern);
$textlen = strlen($text);
$table = makeCharTable($pattern);

for ($i = $patlen - 1; $i < $textlen;) {

$t = $i;
for ($j = $patlen - 1; $pattern[$j] == $text[$i]; $j--, $i--) {
if ($j == 0) return $i;
}
$i = $t;
if (array_key_exists($text[$i], $table))
$i = $i + max($table[$text[$i]], 1);
else
$i += $patlen;
}
return -1;
}

function makeCharTable($string)

{
$len = strlen($string);
$table = array();
for ($i = 0; $i < $len; $i++) {
$table[$string[$i]] = $len - $i - 1;
}
return $table;
}
$data = "the quick brown fox jumps over the lazy dog";

$value = BoyerMoore($data, "the");

echo "
";

var_dump($value);

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:


Masalan, yuqoridagi holatda ishlash vaqti O((N-M) * M) ga teng.