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