Minimum Unique Substrings and Maximum Repeats

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Ilie, Lucian | Smyth, William F.^;

Affiliations: Department of Computer Science, University of Western Ontario, London ON N6A 5B7, Canada. ilie@csd.uwo.ca | Department of Computing and Software, McMaster University, Hamilton ON L8S 4K1, Canada | Digital Ecosystems and Business Intelligence Institute, Curtin University of Technology, Perth WA 6845, Australia. smyth@mcmaster.ca

Note: [] Address for correspondence: Department of Computer Science, University ofWestern Ontario, London ON N6A 5B7, Canada

Abstract: Unique substrings appear scattered in the stringology literature and have important applications in bioinformatics. In this paper we initiate a study of minimum unique substrings in a given string; that is, substrings that occur exactly once while all their substrings are repeats. We discover a strong duality between minimum unique substrings and maximum repeats which, in particular, allows fast computation of one from the other. We give several optimal algorithms, some of which are very simple and efficient. Their combinatorial properties are investigated and a number of open problems are proposed.

DOI: 10.3233/FI-2011-536

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 183-195, 2011