Output details
11 - Computer Science and Informatics
King's College London
Output title
Computing the Maximal-Exponent Repeats of an Overlap-Free String in Linear Time
Type
E - Conference contribution
Name of conference/published proceedings
String Processing and Information Retrieval : 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings
Volume number
7608
Issue number
-
First page of article
61
ISSN of proceedings
0302-9743
Year of publication
2012
URL
-
Number of additional authors
2
Additional information
<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.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Algorithms and Bioinformatics
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
