Prague Stringology Conference 2026
Thierry Lecroq, Arnaud Lefebvre and Francesco Pio Marino
Computation of Periods and Covers Using Sampling
| Abstract: |
| Identifying regularities in strings, such as periods and covers, is crucial for applications in text compression, computational biology, and pattern recognition. Characters-Distance-Sampling (CDS) is an efficient technique that encodes a string by storing distances between selected pivot characters, accelerating string processing tasks. We apply CDS to compute periods and shortest covers, selecting only the first character as the pivot. This strategy yields optimized computations, achieving speedups of 81 –85 % for period computation and 34 %–40 % for cover detection. These results demonstrate the potential of CDS-based representations for efficient string analysis and broader applications. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |