We consider two repeat finding problems relative to sets of strings:#N#(a) Find the largest substrings that occur in every string of a#N#given set; (b) Find the maximal repeats in a given string that#N#occur in no string of a given set. Our solutions are based on the#N#suffix array construction, requiring#N#  O (m)  memory, where  m  is#N#the length of the longest input string, and#N#  O (n lm)  time, where  n #N#is the the whole input size (the sum of the length of each string in#N#the input). The most expensive part of our algorithms is the#N#computation of several suffix arrays. We give an implementation and#N#experimental results that evidence the efficiency of our algorithms in#N#practice, even for very large inputs.
['Pablo Barenbaum', 'Verónica Becher', 'Alejandro Deymonnaz', 'Melisa Halsband', 'Pablo Ariel Heiber']
Efficient repeat finding in sets of strings via suffix arrays