代码
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;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2010/04/21/1717668.html，如需转载请自行联系原作者
