A Linear Time Algorithm for Seeds Computation

Details A Linear Time Algorithm for Seeds Computation A Linear Time Algorithm for Seeds Computation

2011-07-12

arxiv.org/abs/1107.2422v1

Computer Science

Data Structures and Algorithms

full version of paper submitted to SODA 2012

Scientific paper

Periodicity in words is one of the most fundamental areas of text algorithms and combinatorics. Two classical and natural variations of periodicity are seeds and covers (also called quasiperiods). Linear-time algorithms are known for finding all the covers of a word, however in case of seeds, for the past 15 years only an $O(n\log{n})$ time algorithm was known (Iliopoulos, Moore and Park, 1996). Finding an $o(n\log{n})$ time algorithm for the all-seeds problem was mentioned as one of the most important open problems related to repetitions in words in a survey by Smyth (2000). We show a linear-time algorithm computing all the seeds of a word, in particular, the shortest seed. Our approach is based on the use of a version of LZ-factorization and non-trivial combinatorial relations between the LZ-factorization and seeds. It is used here for the first time in context of seeds. It saves the work done for factors processed earlier, similarly as in Crochemore's square-free testing.

Affiliated with

Also associated with

No associations

Rating

A Linear Time Algorithm for Seeds Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Linear Time Algorithm for Seeds Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Linear Time Algorithm for Seeds Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-164970