shibh308

@shibh308

Joined on Aug 23, 2018

  • 検索や挿入が速いパトリシア木 String Attractorsを用いたランダムアクセス可能なデータ構造 Suffix Treeで解ける有名っぽい問題 ライブラリ(ほぼ)全解説 insert/erase/lower_bound とかが速いデータ構造 スキップリストで区間を管理するやつ DAWG初出論文のメモ Hypertext Matchingの雑まとめ (+Parameterized Matching)
     Like  Bookmark
  • The Smallest Automaton Recognizing The Subwords of a Text 内容 右同値類とDAWGの定義 end-set(出現位置の右端の集合) に対して end-equivalentみたいな概念を作る 右同値類に対する補題 右同値類が一致しているなら片方が片方のsuffixになる 出現位置が一定数ズレて一致している
     Like  Bookmark
  • 前提 $S$ : テキスト文字列 $n$ : $S$ の文字列長 $\sigma$ : アルファベットサイズ $\Gamma$ : String Attractorsの要素 $\gamma$ : String Attractorsのサイズ $w$ : ワードサイズ とする
     Like  Bookmark