A Linear-Time Algorithm for Seeds Computation
A Linear-Time Algorithm for Seeds Computation
A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. Our first contribution is a linear-time algorithm computing a linear-size representation of all seeds of a word (the number of seeds might be quadratic). In particular, one can …