3 papers
cs.DS2020
Cadences in Grammar-Compressed Strings
Julian Pape-Lange
Cadences are structurally maximal arithmetic progressions of indices corresponding to equal characters in an underlying string. This paper provides a polynomial time detection algo…
cs.DS2020
On Extensions of Maximal Repeats in Compressed Strings
Julian Pape-Lange
This paper provides an upper bound for several subsets of maximal repeats and maximal pairs in compressed strings and also presents a formerly unknown relationship between maximal…
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…