3 citations · 11 across the 16 of their papers we have counts for
20 papers
Height-bounded Lempel-Ziv encodings
Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian +2
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access…
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
Kento Iseri, Tomohiro I, Diptarama Hendrian +3
A parameterized string (p-string) is a string over an alphabet , where and are disjoint alphabets for static symbols (s-symbols) and for paramet…
Efficient Parameterized Pattern Matching in Sublinear Space
Haruki Ideguchi, Diptarama Hendrian, Ryo Yoshinaka +1
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern in a text . In considering matching alg…
Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga +2
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string of length has nodes and edges, and the stri…
Inferring Strings from Position Heaps in Linear Time
Koshiro Kumagai, Diptarama Hendrian, Ryo Yoshinaka +1
Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This p…
Computing the Parameterized Burrows--Wheeler Transform Online
Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl +2
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characte…
Parallel algorithm for pattern matching problems under substring consistent equivalence relations
Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka +1
Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation is called a sub…
In-Place Bijective Burrows-Wheeler Transforms
Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian +1
One of the most well-known variants of the Burrows-Wheeler transform (BWT) [Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv 2012], which applies the ex…
Grammar compression with probabilistic context-free grammar
Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka +2
We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string has been compressed as a context-free gramma…
Fast and linear-time string matching algorithms based on the distances of -gram occurrences
Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka +1
Given a text of length and a pattern of length , the string matching problem is a task to find all occurrences of in . In this study, we propose an algorithm…
Parameterized DAWGs: efficient constructions and bidirectional pattern searches
Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian +6
Two strings and over of equal length are said to \emph{parameterized match} (\emph{p-match}) if there is a renaming bijection that…
Computing Covers under Substring Consistent Equivalence Relations
Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka +1
Covers are a kind of quasiperiodicity in strings. A string is a cover of another string if any position of is inside some occurrence of in . The shortest and lon…
Generalized Dictionary Matching under Substring Consistent Equivalence Relations
Diptarama Hendrian
Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary match…
Query Learning Algorithm for Residual Symbolic Finite Automata
Kaizaburo Chubachi, Diptarama Hendrian, Ryo Yoshinaka +1
We propose a query learning algorithm for residual symbolic finite automata (RSFAs). Symbolic finite automata (SFAs) are finite automata whose transitions are labeled by predicates…
An Extension of Linear-size Suffix Tries for Parameterized Strings
Katsuhito Nakashima, Diptarama Hendrian, Ryo Yoshinaka +1
In this paper, we propose a new indexing structure for parameterized strings which we call PLSTs, by generalizing linear-size suffix tries for ordinary strings. Two parameterized s…
Online Algorithms for Constructing Linear-size Suffix Trie
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string of length has nodes and edges, and the string la…
Enumerating Cryptarithms Using Deterministic Finite Automata
Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka +2
A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters tha…
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk
Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka +1
We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk of that graph. It has been known that this problem is solvable in $O(n \l…
Efficient computation of longest single-arm-gapped palindromes in a string
Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisawa +2
In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which…
Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura +2
We consider construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection of texts, where a new symbol may be a…