Output details
11 - Computer Science and Informatics
King's College London
Computing the Maximal-Exponent Repeats of an Overlap-Free String in Linear Time
<12>The detection of repeated segments in strings comes up for example in the design of text compression, indexing and genome assembly methods. The article provides a linear-time algorithm for finding the most significant of them when their occurrences never overlap (known solutions otherwise). The criterion is the string's exponent (quotient of string’s length over string’s smallest period). The solution includes both a sophisticated technique based on automata and a combinatorial discovery about the linear number of maximal-exponent segments. The paper was given the Best Paper award of SPIRE'2012, specialised conference on String Processing.