Showing 2019 · cs.DSShow all
2 papers · 2 filters
cs.DS2019
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…
cs.DS2019
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…