ポジションヒープ(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.

可視化

文字列を入力してください.
Text=
Pattern=