Mavzu : matnda qidiruv algoritimini tahlil qilish

To’liq codi:
Php:

function SearchString($str, $pat)

{
$retVal = array();

$N = strlen($str); // uzuligi = 43

$M = strlen($pat); // uzunligi = 3
$i = 0;
$j = 0;
$lps = array();

ComputeLPSArray($pat, $M, $lps);

while ($i < $N)

{
if ($pat[$j] == $str[$i])
{
$j++;
$i++;
}

if ($j == $M)

{
array_push($retVal, $i - $j);
$j = $lps[$j - 1];
}

else if ($i < $N && $pat[$j] != $str[$i])

{
if ($j != 0)
$j = $lps[$j - 1];
else
$i = $i + 1;
}
}

return $retVal;

}
function ComputeLPSArray($pat, $m, &$lps)
{
// pat = "the"
$len = 0;
$i = 1;

$lps[0] = 0;

while ($i < $m ) // uzunligigacha 3

{
if ($pat[$i] == $pat[$len])
{
$len++;
$lps[$i] = $len;
$i++;
}
else
{
if ($len != 0)
{
$len = $lps[$len - 1];
}
else
{
$lps[$i] = 0;
$i++;
}
}
}
}
$data = "the quick brown fox jumps over the lazy dog";

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

echo "
";

var_dump($value);

Matn ichida qidiruv. Boyer-Moore algoritmi

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.

Dastlabki tekshirilayotgan belgi – E matnning dastlabki M-elementiga teng emas (N != E). Ammo N pattern ichida bor. Keyingi tekshirish uchun pointerni N qilib belgilaymiz.

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).

E == E lekin keyingi element N != L. Patternda N bor. Keyingi tekshirish uchun pointerni mana shu Nga beramiz.

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.