106 citations · 249 across the 101 of their papers we have counts for
7 papers · 1 filter
Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka +1
The dictionary matching is a task to find all occurrences of patterns in a set (called a dictionary) on a text . The Aho-Corasick-automaton (AC-automaton) is a data structur…
Order preserving pattern matching on trees and DAGs
Temma Nakamura, Shunsuke Inenaga, Hideo Bannai +1
The order preserving pattern matching (OPPM) problem is, given a pattern string and a text string , find all substrings of which have the same relative orders as . In…
Linear-size CDAWG: new repetition-aware indexing and grammar compression
Takuya Takagi, Keisuke Goto, Yuta Fujishige +2
In this paper, we propose a novel approach to combine \emph{compact directed acyclic word graphs} (CDAWGs) and grammar-based compression. This leads us to an efficient self-index,…
On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga +3
We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally…
Faster STR-IC-LCS computation via RLE
Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga +2
The constrained LCS problem asks one to find a longest common subsequence of two input strings and with some constraints. The STR-IC-LCS problem is a variant of the constra…
Small-space encoding LCE data structure with constant-time queries
Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai +2
The \emph{longest common extension} (\emph{LCE}) problem is to preprocess a given string of length so that the length of the longest common prefix between suffixes of t…