Affiliations: Algorithm Design Group, Department of Computer
Science, King's College London The Strand, London WC2R 2LS,
England. E-mail: csi@dcs.kcl.ac.uk | Digital Ecosystems & Business Intelligence
Institute, Curtin University GPO Box U1987, Perth WA 6845, Australia Digital
Ecosystems & Business Intelligence Institute, Curtin University GPO Box
U1987, Perth WA 6845, Australia. E-mail: yusufum@mcmaster.ca | Algorithms Research Group, Department of Computing
& Software, McMaster University Hamilton, Ontario, Canada L8S 4K1.
E-mail: smyth@mcmaster.ca
Abstract: A repeat in a string is a substring that occurs more than once. A
repeat is extendible if every occurrence of the repeat has an identical letter
either on the left or on the right; otherwise, it is maximal. A multirepeat is
a repeat that occurs at least mmin times (m_{min}⩾ 2) in each of at least q ⩾ 1
strings in a given set of strings. In this paper, we describe a family of
efficient algorithms based on suffix arrays to compute maximal multirepeats
under various constraints. Our algorithms are faster, more flexible and much
more space-efficient than algorithms recently proposed for this problem. The
results extend recent work by two of the authors computing all maximal repeats
in a single string.
