我將如何著手實施Boyer-Moore Search for streams？我了解如何為我們知道整個字符串長度的給定字符串實現這一點。但是，如果我們不知道字符串的大小（即它是任意長度的字節流）怎么辦？我正在嘗試在 PHP 中實現它，因此 PHP 中的任何代碼都會有所幫助。這是我在 PHP 中實現的 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;}如果我們給它一個 haystack string"barfoobazquix"和 needle string 就可以正常工作"foo"，它會3按預期返回。但是，如果輸入 haystack 是一個分成 4 字節塊的流怎么辦。第一個塊是"barf"，它不會返回任何匹配項，第二個塊是 ，"ooba"它也不會返回任何匹配項，依此類推......在這種情況下，我們永遠無法"foo"在當前實現的流的任何緩沖塊中找到子字符串。我正在努力調整當前的實現，以便即使搜索字符串被拆分成多個塊也能正常工作。
1 回答
慕的地10843
TA貢獻1785條經驗 獲得超8個贊
請注意，您只使用$needleLen流中的最新字符。所以你可以維護一個$needleLen由字符組成的滑動窗口，并根據需要推進它。此外，$haystackLen現在是未知的，應該用 EOF 檢查代替。
O(n)下面的代碼效率低下，因為無論我們是按字符滑動窗口n還是僅按 1 個滑動窗口，滑動窗口總是需要時間。為了實現最佳的滑動復雜度，$window應該將其實現為循環字符緩沖區。
// 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 關注
- 166 瀏覽
添加回答
舉報
0/150
提交
取消