Skip to content

Instantly share code, notes, and snippets.

@nticaric
Last active July 16, 2022 08:25
Show Gist options
  • Save nticaric/8147501 to your computer and use it in GitHub Desktop.
Save nticaric/8147501 to your computer and use it in GitHub Desktop.
Boyer–Moore algorithm implementation in PHP
<?php
/**
* Returns the index of the first occurrence of the
* specified substring. If it's not found return -1.
*
* @param text The string to be scanned
* @param pattern The target string to search
* @return The start index of the substring
*/
function BoyerMoore($text, $pattern) {
$patlen = strlen($pattern);
$textlen = strlen($text);
$table = makeCharTable($pattern);
for ($i=$patlen-1; $i < $textlen;) {
$t = $i;
for ($j=$patlen-1; $pattern[$j]==$text[$i]; $j--,$i--) {
if($j == 0) return $i;
}
$i = $t;
if(array_key_exists($text[$i], $table))
$i = $i + max($table[$text[$i]], 1);
else
$i += $patlen;
}
return -1;
}
function makeCharTable($string) {
$len = strlen($string);
$table = array();
for ($i=0; $i < $len; $i++) {
$table[$string[$i]] = $len - $i - 1;
}
return $table;
}
@wildankw123
Copy link

excuse me, I have a case study using this method, I need an explanation of each line of code, can you help me?

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