Prague Stringology Conference 2011
Frantisek Franek, Mei Jiang and Chia-Chun Weng
An Improved Version of the Runs Algorithm Based on Crochemore's Partitioning Algorithm
| Abstract: |
| Though there are in theory linear-time algorithms for computing runs in strings, recently two of the authors implemented an O(n log n) algorithm to compute runs that was based on the Crochemore's partitioning repetitions algorithm. The algorithm preserved the running complexity of the underlying Crochemore's algorithm; however, the static memory requirement – already large at 14n integers for a string of length n – was increased significantly to O(n log n) integers. The purpose and advantage of this algorithm was its speed. In this paper we present a more advanced version of the extension of the Crochemore's algorithm for computing runs. This version in addition to maximal repetitions, computes runs and primitively rooted distinct squares. Its implementation completely does away with the extra memory required for the previous version and through some additional memory saving techniques, the overall memory need was reduced to 13n integers. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |