Boyer和Moore算法，移位表計算

我整晚沒有計算用於Boyer and Moore pattern matching algorithm的搜索詞「anabanana」的簡單移位表。Boyer和Moore算法，移位表計算

我發現沒有任何解釋下面的例子： enter image description here

任何人可以幫助我理解和解釋圖像的方法尋找轉移表？

2013-07-11 J-H

你能提供更多背景嗎？更具體地說，[你有什麼嘗試]（http://whathaveyoutried.com），你知道在這個例子中搜索的文本嗎？ –

我的示例中沒有給出正在搜索的文本。任務是通過使用這種方法來計算可換班表單詞anabanana。我張貼的圖片是解決方案的建議。如果有其他簡單的方法來計算移位表，我也會使用它。所以我的問題是：「如何使用boyer和moore來計算不使用計算機的簡單方法來使用shifttable」thx –

你在哪裏找到這個例子？給我一個鏈接，也許我可以幫助你。 – Sayakiss

我想我明白這裏做了什麼，所以我會嘗試解釋。

行「Wort」是你正在分析的模式，有（在我看來）沒有必要考慮上面的行「文本」。取而代之的是假定一個額外的行，其中包含從左到右的模式中從零開始的char位置。所描繪的圖案p[]的長度m是9. 每一行下面我的名字p_i[]其中i是在右側

進一步說明的指數基於2：

在圖案標記下方的下部行所有與上述模式中的字符匹配的字符。（在這裏完成由劃掉）

for i=1 to m do 
    search in the rows below for a subpattern where p[m-i]<>p_j[m-1] (*) 
    and p[m-i+1, ..., m-1]=p_j[m-i+1, ..., m-1] 
    index j is your shift value for shift[i] 
od

（*）注：當偏移模式p_j得到太遠右移，會出現空字符比較。在這種情況下，您可以根據需要始終假設==或<>。始終使用所有可能的最小值j。

example of assorted steps

我希望這可以幫助，雖然有點晚了。

來源

2013-10-05 00:08:37 marc

嗨，雖然我已經通過了考試，但這是一個很好的和廣泛的解釋，非常感謝你的努力 –

我不得不這樣做，時間和你的問題是我可以從我的課堂筆記中排除的最好的信息，這些信息不是很容易理解，這似乎不是一個容易被教導的算法，實際上我必須感謝你：解釋它幫助我完全理解了這個算法。那次考試非常順利。 – marc

Boyer和Moore算法，移位表計算

回答

相關問題