如何工作Bitap算法?

I'm trying to understand the algorithm Bitap for string matching The following code related to bitap algorithm that write with PHP language :

function SearchString($text, $pattern)
{
$m = strlen($pattern);
$textLen = strlen($text);
$patternMask = array();
$i;

if (empty($pattern)) return 0;
if ($m > 31) return -1; //Error: The pattern is too long!

$R = ~1;

for ($i = 0; $i <= 127; ++$i)
    $patternMask[$i] = ~0;

for ($i = 0; $i < $m; ++$i)
    $patternMask[ord($pattern[$i])] &= ~(1 << $i);

for ($i = 0; $i < $textLen; ++$i)
{
    $R |= $patternMask[ord($text[$i])];
    $R <<= 1;

    if (0 == ($R & (1 << $m)))
        return ($i - $m) + 1;
}

return -1;
}

Please explain how this code works?

i am not understand this part :

for ($i = 0; $i < $m; ++$i)
$patternMask[ord($pattern[$i])] &= ~(1 << $i);

for ($i = 0; $i < $textLen; ++$i)
{
$R |= $patternMask[ord($text[$i])];
$R <<= 1;

if (0 == ($R & (1 << $m)))
    return ($i - $m) + 1;
}

return -1;

thanks

douzhi2988
douzhi2988 这部分:for($i=0;$i<$m;++$i)$patternMask[ord($pattern[$i])]&=〜(1<<$i);for($i=0;$i<$textLen;++$i){$R|=$patternMask[ord($text[$i])];$R<<=1;if(0==($R&(1<<$m)))return($i-$m)+1;}return-1;
接近 4 年之前 回复
duanguai2781
duanguai2781 你能问一个更具体的问题吗?你明白哪条线路?
接近 4 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐