資料結構與演算法
關於在字串中尋找樣式的 BM 法（Boyer-Moore 演算法）的特徵，下列何者正確？
- A從樣式的末尾字元開始比較，並利用「不相符的文本字元不在樣式中」等資訊，一次大幅移動樣式
- B從文本開頭每次移動1個字元，每次都從樣式開頭到最後比較所有字元
- C先把文本與樣式都排序，再以二分搜尋尋找
查看答案與解析
正確答案：A. 從樣式的末尾字元開始比較，並利用「不相符的文本字元不在樣式中」等資訊，一次大幅移動樣式
BM 法從末尾字元開始比較樣式，並事先建立表格，例如若不相符的文本字元完全不在樣式中，就能把整個樣式移到該字元之後。因此在自然語言的文章中，能跳過文本中許多字元而不必比較。設文本長度為 n、樣式長度為 m，每次移動1個字元並全部比較的單純方法，最差需要 O(nm)。KMP 演算法也利用不相符的資訊來移動，但它從樣式開頭比較，最差也保證 O(n + m)。
- A. 正確。從末尾比較，並依不相符字元的資訊大幅移動，就是 BM 法。
- B. 這是單純的（暴力）方法，最差需要 O(nm)。
- C. 這是要找出字串中位置的問題，排序會失去位置的資訊。