Skip to Main content Skip to Navigation
Journal articles

Efficient repeat finding in sets of strings via suffix arrays

Abstract : We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O(m) memory, where m is the length of the longest input string, and O(n &log;m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive part of our algorithms is the computation of several suffix arrays. We give an implementation and experimental results that evidence the efficiency of our algorithms in practice, even for very large inputs.
Document type :
Journal articles
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-00980753
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, April 18, 2014 - 4:43:31 PM
Last modification on : Friday, August 2, 2019 - 3:06:02 PM
Long-term archiving on: : Monday, April 10, 2017 - 3:39:24 PM

File

2130-7867-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00980753, version 1

Collections

Citation

Pablo Barenbaum, Verónica Becher, Alejandro Deymonnaz, Melisa Halsband, Pablo Ariel Heiber. Efficient repeat finding in sets of strings via suffix arrays. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.59--70. ⟨hal-00980753⟩

Share

Metrics

Record views

866

Files downloads

1304