我將如何著手實(shí)施Boyer-Moore Search for streams？我了解如何為我們知道整個(gè)字符串長(zhǎng)度的給定字符串實(shí)現(xiàn)這一點(diǎn)。但是，如果我們不知道字符串的大?。此侨我忾L(zhǎng)度的字節(jié)流）怎么辦？我正在嘗試在 PHP 中實(shí)現(xiàn)它，因此 PHP 中的任何代碼都會(huì)有所幫助。這是我在 PHP 中實(shí)現(xiàn)的 Boyer-Moore 搜索：function BoyerMooreSearch($haystack, $needle) { $needleLen = strlen($needle); $haystackLen = strlen($haystack); $table = computeSkipTable($needle); for ($i = $needleLen - 1; $i < $haystackLen;) { $t = $i; for ($j = $needleLen - 1; $needle[$j] == $haystack[$i]; $j--, $i--) { if($j == 0) { return $i; } } $i = $t; if(array_key_exists($haystack[$i], $table)) { $i = $i + max($table[$haystack[$i]], 1); } else { $i += $needleLen; } } return false;}function computeSkipTable($string) { $len = strlen($string); $table = []; for ($i=0; $i < $len; $i++) { $table[$string[$i]] = $len - $i - 1; } return $table;}如果我們給它一個(gè) haystack string"barfoobazquix"和 needle string 就可以正常工作"foo"，它會(huì)3按預(yù)期返回。但是，如果輸入 haystack 是一個(gè)分成 4 字節(jié)塊的流怎么辦。第一個(gè)塊是"barf"，它不會(huì)返回任何匹配項(xiàng)，第二個(gè)塊是 ，"ooba"它也不會(huì)返回任何匹配項(xiàng)，依此類推......在這種情況下，我們永遠(yuǎn)無法"foo"在當(dāng)前實(shí)現(xiàn)的流的任何緩沖塊中找到子字符串。我正在努力調(diào)整當(dāng)前的實(shí)現(xiàn)，以便即使搜索字符串被拆分成多個(gè)塊也能正常工作。
1 回答
慕的地10843
TA貢獻(xiàn)1785條經(jīng)驗(yàn) 獲得超8個(gè)贊
請(qǐng)注意，您只使用$needleLen流中的最新字符。所以你可以維護(hù)一個(gè)$needleLen由字符組成的滑動(dòng)窗口，并根據(jù)需要推進(jìn)它。此外，$haystackLen現(xiàn)在是未知的，應(yīng)該用 EOF 檢查代替。
O(n)下面的代碼效率低下，因?yàn)闊o論我們是按字符滑動(dòng)窗口n還是僅按 1 個(gè)滑動(dòng)窗口，滑動(dòng)窗口總是需要時(shí)間。為了實(shí)現(xiàn)最佳的滑動(dòng)復(fù)雜度，$window應(yīng)該將其實(shí)現(xiàn)為循環(huán)字符緩沖區(qū)。
// sample call
var_dump(BoyerMooreSearch(STDIN, 'foo'));
function BoyerMooreSearch($resource, $needle) {
$needleLen = strlen($needle);
$table = computeSkipTable($needle);
// build the first window
if (($window = buildWindow($resource, $needleLen)) === false) {
// special case: the text is shorter than the pattern
return false;
}
$i = 0;
while (true) {
// check for a match
$j = $needleLen - 1;
while ($j >= 0 && $needle[$j] == $window[$j]) {
$j--;
}
if ($j < 0) {
return $i;
}
// determine slide distance
$t = $i;
$last = substr($window, -1);
if (array_key_exists($last, $table)) {
$i = $i + max($table[$last], 1);
} else {
$i += $needleLen;
}
// slide the window
if (($window = slideWindow($window, $resource, $i - $t)) === false) {
return false;
}
}
return false;
}
/**
* Initializes the sliding window to length $len.
*
* @return string A string of length $len or false if the $resource contains
* less than $len characters.
*/
function buildWindow ($resource, $len) {
$result = '';
while ($len--) {
$result .= fgetc($resource);
}
return feof($resource) ? false : $result;
}
/**
* Slides $window by $count positions into $resource.
*
* @return string The new window or false on EOF.
*/
function slideWindow(&$window, $resource, $count) {
$window = substr($window, $count) // discard the first $count chars
. fread($resource, $count); // and read $count new chars
return feof($resource) ? false : $window;
}
- 1 回答
- 0 關(guān)注
- 164 瀏覽
添加回答
舉報(bào)
0/150
提交
取消