Locating Maximal Multirepeats in Multiple Strings Under Various Constraints †
A. Bakalis, Costas S. Iliopoulos, Christos H. Makris, Spyros Sioutas, Evangelos Theodoridis, Athanasios Tsakalidis, Kostas Tsichlas · The Computer Journal · 2006
A multirepeat in a string is a substring (factor) that appears a predefined number of times. A multirepeat is maximal if it cannot be extended either to the right or to the left and produce a multirepeat. In this paper, we present algorithms for two different versions of the problem of finding maximal multirepeats in a set of strings. In the case of arbitrary gaps, we propose an algorithm with O ( σN2n + α ) time complexity. When the gap is bounded in a small range c , we propose an algorithm with O (( c2 + σ2 ) mN2n log( Nn ) + α ) time complexity. Here, N is the number of strings, n the mean length of each string, m the multiplicity of the multirepeat and α the number of reported occurrences. Our results extend previous work by considering sets of strings as well as by generalizing pairs to multirepeats.