BMHサブストリングルックアップアルゴリズム(PHP実装)
- interface StringSearchable
- {
- public function search($substring, $buffer);
- }
- class BoyerMooreStringSearch implements StringSearchable
- {
- public $substring = null;
- public $buffer = '';
- public $jumpTable = array();
- protected $results = array();
-
- public function __construct()
- {
-
- }
- public function __destruct()
- {
- }
- public function search($substring, $buffer)
- {
- $this->results = array();
- $this->substring = $substring;
- $this->buffer = $buffer;
- $this->deriveJumpTable();
-
- $substringLen = strlen($this->substring);
- $currentCharIndex = $substringLen - 1;
- $bufferLen = strlen($this->buffer);
- while ($currentCharIndex < $bufferLen) {
- for ($i = $substringLen - 1; $i >= 0; $i--) {
- if ($this->buffer[$currentCharIndex - $substringLen + $i + 1] == $this->substring[$i]) {
- if ($i == 0) {
- $this->results[] = $currentCharIndex - $substringLen;
- $currentCharIndex += $this->getJumpLength($this->buffer[$currentCharIndex]);
- } else {
- continue;
- }
- } else {
- $currentCharIndex += $this->getJumpLength($this->buffer[$currentCharIndex]);
- break;
- }
-
- }
- }
- return (sizeof($this->results) > 0);
- }
-
- protected function deriveJumpTable()
- {
- $maxJump = strlen($this->substring);
- for ($i = strlen($this->substring) - 2; $i >= 0; $i--) {
- if (!array_key_exists($this->substring[$i], $this->jumpTable)) {
- $this->jumpTable[$this->substring[$i]]] = $maxJump - $i -1;
- }
- }
- }
- public function getJumpTable()
- {
- return $this->jumpTable;
- }
- public function getResults()
- {
- return $this->results;
- }
- public function getResultsCount()
- {
- return sizeof($this->results);
- }
- public function getJumpLength($charIndex)
- {
- if (array_key_exists($charIndex, $this->jumpTable)) {
- return $this->jumpTable[$charIndex];
- } else {
- return strlen($this->substring);
- }
- }
- }
-
- function Main()
- {
- $poem = <<<POEM
- you son of bitch
- god damn it
- hey,god love me
- POEM;
- $bm = new BoyerMooreStringSearch();
- $bm->search('god', $poem);
- $count = $bm->getResultsCount;
- echo $count;
- }