Can you summarize the following document?
        
  </div> 當T中有字元不匹配時,如果T中的這個不匹配的字元出現在對應P中當前位置的左側,那麼P移動位置將這兩個在字元對齊。如果T中這個不匹配字元不在P中當前位置的左側,那麼將當前位置左側的所有字元均移到該不匹配字元後。右側的例子中,X位置發生了不匹配,我們檢查P中的不匹配字元N(對應T中字元A)在P當前位置(X)的左側存在,因此,將最靠近該不匹配字元位置的N與P中的X位置的N對齊,也就是向右移動兩位。

  當我們發現不匹配字元時,假設這個字元在T中為c,位置在T的i。字元c在P中出現的最靠近i位置,假設為j,j<i或j=-1(如果P不存在字元c)。那麼移動位數為i - j,複雜度是O(1)。i,j的起點為P在T中位置的開始T[(k-n+1)..k]的(k-n+1)。 大多網站都只建立一個一維壞字元陣列來儲存,但事實這隻能儲存最靠左或最靠右的字元c,明顯與英文的wikipedia裡面要求一個二維陣列來儲存資訊的不一樣。

  

  好字尾規則要更復雜一點。  假設有P和T,T中字串t匹配到了P的一個字尾,但在比較位置i時發生不匹配。設匹配到的好字尾在T中為t,在P中為t'(t = t')。  分兩種情況來討論:  1,在P中i位置的左側最靠近i位置查詢字串t'使得t'=t(此時t'不是P的字尾,實際上也就是查詢匹配到的字串除了在P的字尾中存在,是否在P的其他位置存在),若存在,則移動相應的位數將找到的t'與T中的t對齊。  2,如果t'不存在,那我們繼續查詢t的某一個字尾是否為P的字首,若存在,則移動相應的位將P的字首與t的字尾位置對齊。否則,將P向後移動n個字元。  好字尾規則的實質是,將不匹配位置右側匹配到的字串t的所有字元字尾組合,用於查詢它們在P的不匹配位置左側是否存在。  通俗的理解是,最長的好字尾t是否存在於i的左側(情況1),其他字尾組合中是否存在與P的字首相同的情況(情況2)。

  假設被檢索文字列是“1234567890”,檢索文字列是“MOORE”。簡單的比較需要執行十次才得到結論不匹配。被檢索文字列:1234567890  ※未參與比較的文字用【.】佔位。  BM演算法只需要2次比較。  被檢索文字列:1234567890  第一次從檢索文字的末尾開始,因為如果被檢索文字的第5文字位置不是E,則無論前4個文字是什麼,都絕不可能匹配了。這一點比較容易理解。  而之所以不用E和6比較,則是因在E和5進行比較的時候不僅知道他們不相等,而且還知道了5不和檢索文字MOORE中的任何一個文字相等,這使得下面這些比較都可以省略掉。  被檢索文字列:...5...
在電腦科學裡,Boyer-Moore字串搜尋演算法是一種非常高效的字串搜尋演算法。它由Bob Boyer和J Strother Moore設計於1977年。此演算法僅對搜尋目標字串(關鍵字)進行預處理,而非被搜尋的字串。雖然Boyer-Moore演算法的執行時間同樣線性依賴於被搜尋字串的大小,但是通常僅為其它演算法的一小部分:它不需要對被搜尋的字串中的字元進行逐一比較,而會跳過其中某些部分。通常搜尋關鍵字越長,演算法速度越快。它的效率來自於這樣的事實:對於每一次失敗的匹配嘗試,演算法都能夠使用這些資訊來排除儘可能多的無法匹配的位置。