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) 

이다 - 그러므로 또한 공헌 -은 일치하는 창에 length(pattern)-1 개 문자 각각에 대해 radix을 곱하여 c이 마침내 나타납니다.

하지만 당신은 계산에서 당신이 $this->previousHash해야한다 0으로 설정 한 변수 $txtHash을, 사용하고, 또한

$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; 

ord(c) * radix * length(pattern)을 뺀거야, 당신은 텍스트의 위치를 ​​증가한다 . 원칙적으로

,

$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; 

은 당신이해야 할 것입니다.

그러나 패턴이 매우 짧은 경우를 제외하고는 모듈 식 지수 함수

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; 
} 

와 pow($this-radix, strlen($this->pattern)-1)를 교체해야하므로, pow($this->radix,strlen($this->pattern)-1)는 오버플로 (즉 여기 $this->prime입니다 $modulus 경우이 수 여전히 오버 플로우가 너무 큰). 코드의 해당 줄은 잠재적으로 거대한 비 효율성

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

문자열이 긴 될 경우, 연결 및 분리 방법 PHP 구현 확실하지 (시간이 많이 걸릴 수있는 그런

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

된다 문자열 및 문자열 연산이 있지만 일정 시간이 아닐 수도 있습니다. 문자열의 관련 부분 만 유지해야합니다. 즉 해시를 다시 계산 한 후 첫 번째 문자를 삭제해야합니다.