douhe6181 2016-11-29 16:21
浏览 87

如何工作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

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥65 永磁型步进电机PID算法
    • ¥15 sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?
    • ¥88 找成都本地经验丰富懂小程序开发的技术大咖
    • ¥15 如何处理复杂数据表格的除法运算
    • ¥15 如何用stc8h1k08的片子做485数据透传的功能?(关键词-串口)
    • ¥15 有兄弟姐妹会用word插图功能制作类似citespace的图片吗?
    • ¥200 uniapp长期运行卡死问题解决
    • ¥15 latex怎么处理论文引理引用参考文献
    • ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
    • ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?