基于PHP的Rabin-Karp算法

Question

我想知道是否有人可以分享Rabin-Karp算法的源码？

谢谢

Answer 1

http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node43.html

这里有几个消息来源。

Answer 2

这是this C implementation of the Karp-Rabin algorithm的一个端口

function KR($haystack, $needle) {
    $n = strlen($haystack);
    $m = strlen($needle);
    if ($m > $n) {
        return -1;
    }
    /* Preprocessing */
    $d = 1 << ($m - 1);
    for ($hh = $hn = $i = 0; $i < $m; ++$i) {
        $hh = (($hh<<1) + ord($haystack[$i]));
        $hn = (($hn<<1) + ord($needle[$i]));
    }
    /* Searching */
    $j = 0;
    while ($j <= $n-$m) {
        if ($hh == $hn && substr($haystack, $j, $m) === $needle) {
            return $j;
        }
        if ($j === $n-$m) {
            return false;
        }
        /* Rehashing */
        $hh = (($hh - ord($haystack[$j]) * $d) << 1) + ord($haystack[$j + $m]);
        ++$j;
    }
    return false;
}

Answer 3

为了说明起见，这里有一个稍微修改过的版本Gumbo上面的答案，使用了更简单的散列和更清晰的变量命名。

在下面的说明性散列中，我只是将每个字符的ord()值添加到一个表示散列的数字中，然后在推进搜索时减去该值/添加下一个字符的ord()。这是非常容易发生冲突的(因此对生产不好)，但如果你只是从概念上学习拉宾-卡普，它更容易理解。

function rk ($needle, $haystack)
{
    $nlen = strlen($needle);
    $hlen = strlen($haystack);
    $nhash = 0;
    $hhash = 0;

    // Special cases that don't require the rk algo:
    // if needle is longer than haystack, no possible match
    if ($nlen > $hlen) {
        return false;
    }
    // If they're the same size, they must just match
    if ($nlen == $hlen) {
        return ($needle === $haystack);
    }

    // Compute hash of $needle and $haystack[0..needle.length]
    // This is a very primitive hashing method for illustrative purposes
    // only. You'll want to modify each value based on its position in
    // the string as per Gumbo's example above (left shifting)
    for ($i = 0; $i < $nlen; ++$i) {
        $nhash += ord($needle[$i]);
        $hhash += ord($haystack[$i]);
    }

    // Go through each position of needle and see if
    // the hashes match, then do a comparison at that point
    for ($i = 0, $c = $hlen - $nlen; $i <= $c; ++$i) {
        // If the hashes match, there's a good chance the next $nlen characters of $haystack matches $needle
        if ($nhash == $hhash && $needle === substr($haystack, $i, $nlen)) {
            return $i;
        }
        // If we've reached the end, don't try to update the hash with
        // the code following this if()
        if ($i == $c) {
            return false;
        }

        // Update hhash to the next position by subtracting the
        // letter we're removing and adding the letter we're adding
        $hhash = ($hhash - ord($haystack[$i])) + ord($haystack[$i + $nlen]);
    }

    return false;
}