摘要：This paper provides upper bounds for several subsets of maximal repeats and maximal pairs in compressed strings and also presents a formerly unknown relationship between maximal pairs and the run-length Burrows-Wheeler transform. This relationship is used to obtain a different proof for the Burrows-Wheeler conjecture which has recently been proven by Kempa and Kociumaka in "Resolution of the Burrows-Wheeler Transform Conjecture". More formally, this paper proves that the run-length Burrows-Wheeler transform of a string S with z_S LZ77-factors has at most 73(logâ,, S )(z_S+2)² runs, and if S does not contain q-th powers, the number of arcs in the compacted directed acyclic word graph of S is bounded from above by 18q(1+log_q S )(z_S+2)².
关键词：Maximal repeats; Extensions of maximal repeats; Combinatorics on compressed strings; LZ77; Burrows-Wheeler transform; Burrows-Wheeler transform conjecture; Compact suffix automata; CDAWGs
