ポジションヒープ（Position Heaps）
===========================================================



定義
------------------------
* 構築O(n)マッチングO(m+occ)でできるデータ構造
	

参考文献
---------------------------
	* A.Ehrenfeucht, R.McConnell, N.Osheim, and S.-W. Woo. Position heaps: A simple and dynamic text indexing data structure. Journal of Discrete Algorithms, 9(1):100 – 121, 2011.
	* Preliminary version in Proc. 20th Anniversary Edition of the Annual Symposium on Combinatorial Pattern Matching (CPM 2009).
	* Gregory Kucherov. On-Line Construction of Position Heaps. Lecture Notes in Computer Science, 2011, Volume 7024/2011, 326-337.
 

可視化
------------

.. raw:: html

 <script src="../_static/raphael-min.js" type="text/javascript"></script>
 <script src="../_static/PositionHeaps.js" type="text/javascript"></script>
 <div style="width:800px;height:600px">
 <div style="float:left;width:800px">
 文字列を入力してください．<BR>
 <span>Text=</span><input id="INPUT" type="text" value="aababbbaabaab"/>
 </div>
 <div style="float:left;width:800px">
 <span>Pattern=</span><input id="PATTERN" type="text" value="ab"/>
 <input id="MATCH" type="button" value="Match"/></div>
 <div id="OUTPUT" style="float:left"></div>
 
 </div>