Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Output-Sensitive Construction of CDAWGs from BWT-Runs
Yuta Tsuruzono, Hiroki Arimura, Shunsuke Inenaga
The compact directed acyclic word graph (CDAWG) of a string can be viewed in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix…
cs.DS2026
Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
Taiki Kaneda, Hiroki Arimura, Shunsuke Inenaga
We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structu…