PHPを使ったRabin-Karpアルゴリズムの実装

Question

こんにちは私はRabin-Karpアルゴリズムを実装するPHPクラスを作成しています。私は再ハッシング部分で問題があります。このコードには、文字の一部に一致するものは含まれません。私は再ハッシングの問題のためにハッシュコードと決して一致しないので、私は止めなければならなかった。誰かがそれを理解するのを助けてください。

<?php 
class RabinKarp 
{ 
    /** 
    * @var String 
    */ 
    private $pattern ; 
    private $patternHash ; 
    private $text ; 
    private $previousHash ; 

    /** 
    * @var Integer 
    */ 
    private $radix ; 
    private $prime ; 
    private $position ; 

    /** 
    * Constructor 
    * 
    * @param String $pattern - The pattern 
    * 
    */ 
    public function __construct($pattern) 
    { 
     $this->pattern = $pattern; 
     $this->radix = 256; 
     $this->prime = 100007; 
     $this->previousHash = ""; 
     $this->position = 0; 
     $this->patternHash = $this->generateHash($pattern); 
    } 

    private function generateHash($key) 
    { 
     $charArray = str_split($key); 
     $hash = 0; 
     foreach($charArray as $char) 
     { 
      $hash = ($this->radix * $hash + ord($char)) % $this->prime; 
     } 

     return $hash; 
    } 

    public function search($character) 
    { 
     $this->text .= $character; 
     if(strlen($this->text) < strlen($this->pattern)) 
     { 
      return false; 
     } 
     else 
     { 
      $txtHash = 0; 
      echo $this->previousHash . "<br/>"; 
      if(empty($this->previousHash)) 
      { 
       $txtHash = $this->generateHash($this->text); 
       $this->previousHash = $txtHash; 
       $this->position = 0; 
      } 
      else 
      { 
       // The issue is here 
       $charArray = str_split($this->text); 
       $txtHash = (($txtHash + $this->prime) - $this->radix * strlen($this->pattern) * ord($charArray[$this->position]) % $this->prime) % $this->prime; 
       $txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime; 

       $this->previousHash = $txtHash; 
      } 

      if($txtHash == $this->patternHash) 
      { 
       echo "Hash Match found"; 
      } 
     } 

    } 

} 

$x = new RabinKarp("ABC"); 
$x->search("Z"); 
$x->search("A"); 
$x->search("B"); 
$x->search("C"); 
?> 

ありがとうございます。文字は、それが最初のマッチング・ウィンドウに入ったときord(c)を寄与し、ハッシュ以来

Answer 1

値には、削除しようとしているキャラクター（息切れのためc）によってハッシュに貢献

ord(c) * radix^(length(pattern)-1) 

である - したがって、そのcが最終的にそれを残すまで、対応するウィンドウに入力するlength(pattern)-1文字のそれぞれに対して、貢献度 - radixを掛けます。

しかし、あなたはまた、計算にあなたはそれが$this->previousHashする必要があり、あなたは0に設定した変数$txtHashを、使用している、とあなたがテキストの位置をインクリメントする必要がありますord(c) * radix * length(pattern)

$charArray = str_split($this->text); 
$txtHash = (($txtHash + $this->prime) 
      - $this->radix * strlen($this->pattern) 
      * ord($charArray[$this->position]) % $this->prime) 
      % $this->prime; 
$txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime; 

を引いています。原則として

、

$charArray = str_split($this->text); 
$txtHash = (($this->previousHash + $this->prime) 
      - pow($this->radix, strlen($this->pattern)-1) 
      * ord($charArray[$this->position]) % $this->prime) 
      % $this->prime; 
$txtHash = ($txtHash * $this->radix + ord($character)) % $this->prime; 

$this->previousHash = $txtHash; 
$this->position += 1; 

は、あなたがしなければならないものです。

しかし、パターンが非常に短い場合を除き、あなたは、べき乗剰余演算機能付きpow($this-radix, strlen($this->pattern)-1)

function mod_pow($base,$exponent,$modulus) 
{ 
    $aux = 1; 
    while($exponent > 0) { 
     if ($exponent % 2 == 1) { 
      $aux = ($aux * $base) % $modulus; 
     } 
     $base = ($base * $base) % $modulus; 
     $exponent = $exponent/2; 
    } 
    return $aux; 
} 

（これはオーバーフロー$modulus場合はまだすることができを交換する必要がありますので、pow($this->radix,strlen($this->pattern)-1)は、オーバーフローする、それがここに$this->primeあり、大きすぎます）。コードの該当する行が

$txtHash = (($this->previousHash + $this->prime) 
      - mod_pow($this->radix, strlen($this->pattern)-1, $this->prime) 
      * ord($charArray[$this->position]) % $this->prime) 
      % $this->prime; 

なりそうすれば、文字列が長くなると、連結と分割がどのようにPHP実装わからない（多くの時間がかかることがあり、潜在的に巨大な非効率性

$this->text .= $character; 
... 
    $charArray = str_split($this->text); 

を持っています文字列操作、文字列操作などがありますが、それらはおそらく一定時間ではありません）。おそらく、文字列の関連部分だけを保持する必要があります。つまり、ハッシュを再計算した後に最初の文字を削除します。