106 citations · 187 across the 45 of their papers we have counts for
46 papers · 1 filter
Online Computation of Palindromes and Suffix Trees on Tries
Hiroki Shibata, Mitsuru Funakoshi, Takuya Mieno +5
We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tre…
Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga +2
The directed acyclic word graph (DAWG) of a string of length is the smallest (partial) DFA which recognizes all suffixes of with only nodes and edges. In this pa…
Computing maximal palindromes in non-standard matching models
Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima +3
Palindromes are popular and important objects in textual data processing, bioinformatics, and combinatorics on words. Let be a string where and are of the same le…
On the approximation ratio of LZ-End to LZ77
Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi +3
A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kref…
Grammar Index By Induced Suffix Sorting
Tooru Akagi, Dominik Köppl, Yuto Nakashima +3
Pattern matching is the most central task for text indices. Most recent indices leverage compression techniques to make pattern matching feasible for massive but highly-compressibl…
Compressed Communication Complexity of Hamming Distance
Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga +2
We consider the communication complexity of the Hamming distance of two strings. Bille et al. [SPIRE 2018] considered the communication complexity of the longest common prefix (LCP…