Name
Abstract | ||
|---|---|---|
A seed in a word is a relaxed version of a period. We show a linear time algorithm computing a compact representation of all the seeds of a word, in particular, the shortest seed. Thus, we solve an open problem stated in the survey by Smyth (2000) and improve upon a previous over 15-year old O(n log n) algorithm by Iliopoulos, Moore and Park (1996). Our approach is based on combinatorial relations between seeds and a variant of the LZ-factorization (used here for the first time in context of seeds). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.5555/2095116.2095202 | Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms |
Keywords | DocType | Volume |
compact representation,combinatorial relation,linear time algorithm,seeds computation,open problem,15-year old o,shortest seed,n log n,data structure | Conference | abs/1107.2422 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 13 | 0.64 |
References | Authors | |
29 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomasz Kociumaka | 1 | 217 | 38.57 |
| Marcin Kubica | 2 | 629 | 29.26 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Tomasz Waleń | 5 | 706 | 39.62 |