Efficient Computation of Periods and Covers Using Sampling

Identifying regularities in strings, such as \emph{periods} and \emph{covers}, is crucial for applications in text compression, computational biology, and pattern recognition. \emph{Characters-Distance-Sampling} ($\mathtt{\text{CDS}}$) is an efficient technique that encodes a string by storing distances between selected pivot characters, accelerating string-processing tasks. We apply $\mathtt{\text{CDS}}$ to compute periods and shortest covers, selecting only the first character as the pivot. This strategy yields optimized computations, achieving speedups of $38\mathrm{\%}$–$43\mathrm{\%}$ for period computation and $63\mathrm{\%}$–$72\mathrm{\%}$ for cover detection. These results demonstrate the potential of $\mathtt{\text{CDS}}$-based representations for efficient string analysis and broader applications.