BMH子串查找算法(PHP实现)

代码

<!--<br/ /><br/ />Code highlighting produced by Actipro CodeHighlighter (freeware)<br/ />http://www.CodeHighlighter.com/<br/ /><br/ />-->interfaceStringSearchable
{
publicfunctionsearch($substring,$buffer);
}
classBoyerMooreStringSearchimplementsStringSearchable
{
public$substring=null;
public$buffer='';
public$jumpTable=array();
protected$results=array();

publicfunction__construct()
{

}
publicfunction__destruct()
{
}
publicfunctionsearch($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);
}

protectedfunctionderiveJumpTable()
{
$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;
}
}
}
publicfunctiongetJumpTable()
{
return$this->jumpTable;
}
publicfunctiongetResults()
{
return$this->results;
}
publicfunctiongetResultsCount()
{
returnsizeof($this->results);
}
publicfunctiongetJumpLength($charIndex)
{
if(array_key_exists($charIndex,$this->jumpTable)){
return$this->jumpTable[$charIndex];
}else{
returnstrlen($this->substring);
}
}
}

functionMain()
{
$poem=<<<POEM
yousonofbitch
goddamnit
hey,godloveme
POEM;
$bm=newBoyerMooreStringSearch();
$bm->search('god',$poem);
$count=$bm->getResultsCount;
echo$count;
}