Efficient Computation of Periods and Covers Using Sampling

Abstract

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} (\texttt{CDS}) is an efficient technique that encodes a string by storing distances between selected pivot characters, accelerating string-processing tasks. We apply \texttt{CDS} to compute periods and shortest covers, selecting only the first character as the pivot. This strategy yields optimized computations, achieving speedups of $38\%$--$43\%$ for period computation and $63\%$--$72\%$ for cover detection. These results demonstrate the potential of \texttt{CDS}-based representations for efficient string analysis and broader applications.