7 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…
Computing palindromes on a trie in linear time
Takuya Mieno, Mitsuru Funakoshi, Shunsuke Inenaga
A trie is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually dist…
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…
Minimal unique palindromic substrings after single-character substitution
Mitsuru Funakoshi, Takuya Mieno
A palindrome is a string that reads the same forward and backward. A palindromic substring of a string is called a minimal unique palindromic substring (MUPS) of if …
Detecting -(Sub-)Cadences and Equidistant Subsequence Occurrences
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga +3
The equidistant subsequence pattern matching problem is considered. Given a pattern string and a text string , we say that is an \emph{equidistant subsequence} of if…
Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
Mitsuru Funakoshi, Julian Pape-Lange
The discrete acyclic convolution computes the 2n-1 sums sum_{i+j=k; (i,j) in [0,1,2,...,n-1]^2} (a_i b_j) in O(n log n) time. By using suitable offsets and setting some of the vari…