.. -*- coding: utf-8; -*-

.. raw:: html

	 <link rel="stylesheet" href="../../_static/style.css" type="text/css" />

Boyer-Moore法
==================================================

照合方法
----------------------

| Algorithm BM(Jewels of Stringology P.28) :download:`/Scripts/Python/BM.py` 
| j文字目で不一致になった時のシフト量を　:math:`BM＿Shift[j]` と定義する． 

.. literalinclude:: /Scripts/Python/BM.py
   :pyobject: BM

シフト量の計算
----------------------
   
| 与えられたパターンのBMShiftの計算  
| 計算に :doc:`../Basic/period`　を用いる．

.. literalinclude:: /Scripts/Python/BMS.py
   :pyobject: calcBMShift
   

.. literalinclude:: /Scripts/Python/BMS.py
   :pyobject: calcPreBMShift
   
PREF[i]を用いたS[i]の計算

.. note::
    :math:`PREF[i] = max` { :math:`j:pat[i...i+j-1]がpatの` :doc:`../Basic/prefix` } 
	:math:`S[i]`　i番目で終わる部分文字列とパターンの共通接尾辞の最大長　

.. literalinclude:: /Scripts/Python/BMS.py
   :pyobject: calcSuff

   
PREF[i]の計算（素朴な方法）

.. literalinclude:: /Scripts/Python/BMS.py
   :pyobject: calcPref0
   
S[i]を用いた　:doc:`../Basic/period`　の計算

.. literalinclude:: /Scripts/Python/BMS.py
   :pyobject: calcFullPd

   
   
マッチングの実行状態を出力(作成中)
-----------------------------------------

.. raw:: html
         
         
		<div class="algorithm-sample">
		<script type="text/javascript"  src="../../_static/matching-BM.js" > </script>

		<form onsubmit="return false;" autocomplete="off">
		<label> text = <input id="str_text" type="text" size="40" value="babababaababaabababababb"/></label>
		<br />
		<label> pattern = <input id="str_pattern" type="text" size="40" value="abaababa"/></label>
		<br />
		</form>
		<br />
		<div id="match_table" ></div>
		</div>
   

参考文献
--------
 - R.S. Boyer and J.S. Moore, “A fast string searching algorithm.”, Communications of the ACM, Volume 20, Issue 10, pp.762-772, 1977 <http://dl.acm.org/citation.cfm?id=359859>