Skip to content

Instantly share code, notes, and snippets.

@freekrai
Created February 24, 2012 19:32
Show Gist options
  • Save freekrai/1903167 to your computer and use it in GitHub Desktop.
Save freekrai/1903167 to your computer and use it in GitHub Desktop.
Boyer-Moore-Horspool string matching algorithm
<?php
define('UCHAR_MAX',255);
function boyermoore_horspool_memmem($haystack,$needle){
$hlen = strlen($haystack);
$nlen = strlen($needle);
$scan = 0;
$bad_char_skip[UCHAR_MAX + 1];
if ($nlen <= 0 || !$haystack || !$needle) { return NULL; }
for ($scan = 0; $scan <= UCHAR_MAX; $scan = $scan + 1)
$bad_char_skip[$scan] = $nlen;
$last = $nlen - 1;
for ($scan = 0; $scan < $last; $scan = $scan + 1)
$bad_char_skip[$needle[$scan]] = $last - $scan;
while ($hlen >= $nlen){
for ($scan = $last; $haystack[$scan] == $needle[$scan]; $scan = $scan - 1)
if ($scan == 0) { return $haystack; }
$hlen -= $bad_char_skip[$haystack[$last]];
$haystack += $bad_char_skip[$haystack[$last]];
}
return NULL;
}
?>
@otanodesignco
Copy link

This is my code from code4expert.com you could at least not copy other peoples code dude.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment