106 citations · 111 across the 3 of their papers we have counts for
3 papers
cs.DS2020
Grammar-compressed Self-index with Lyndon Words
Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima +3
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data struc…
cs.DS2019★ 5 cited
c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda +4
Given a dynamic set of strings of total length whose characters are drawn from an alphabet of size , a keyword dictionary is a data structure built on that provi…
cs.DM2014★ 106 cited
The "Runs" Theorem
Hideo Bannai, Tomohiro I, Shunsuke Inenaga +3
We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture (…