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条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 安卓adb backup备份应用数据失败
    • ¥15 eclipse运行项目时遇到的问题
    • ¥15 关于#c##的问题:最近需要用CAT工具Trados进行一些开发
    • ¥15 南大pa1 小游戏没有界面,并且报了如下错误,尝试过换显卡驱动,但是好像不行
    • ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
    • ¥50 成都蓉城足球俱乐部小程序抢票
    • ¥15 yolov7训练自己的数据集
    • ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
    • ¥15 电力市场出清matlab yalmip kkt 双层优化问题
    • ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)