4 papers
A Separation of and via Thue--Morse Words
Hideo Bannai, Mitsuru Funakoshi, Tomohiro I +3
We prove that for , the size of the smallest bidirectional scheme for the th Thue--Morse word is . Since Kutsukake et al. [SPIRE 2020] show that the…
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…
Computing longest palindromic substring after single-character or block-wise edits
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga +2
Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of…