A Basis for Repeated Motifs in Pattern Discovery and Text Mining
Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie‐France Sagot · HAL (Le Centre pour la Communication Scientifique Directe) · 2002
We present a new notion of basis that is able to generate the repeated motifs (possibly exponential in number) that appear at least twice with don't care symbols in a string of length n over an alphabet . Our basis has some interesting features such as being (a) a subset of the previously defined bases, (b) truly linear as its motifs are less than n in number and appear in the string for a total of 2n times at most; (c) symmetric as the basis of the reversed string is the reverse of the basis; (d) computable in polynomial time, namely, in O(n log n log j j) time. In addition, several other computational questions related to the use of our basis are discussed. Our notion provides the best-known tradeoff between the size of the basis and the complexity of its construction.