کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430924 | 688233 | 2012 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On left and right seeds of a string On left and right seeds of a string](/preview/png/430924.png)
We consider the problem of finding the repetitive structure of a given string y of length n. A factor u of y is a cover of y, if every letter of y lies within some occurrence of u in y. A string v is a seed of y, if it is a cover of a superstring of y. A left seed of y is a prefix of y, that is a cover of a superstring of y. Similarly, a right seed of y is a suffix of y, that is a cover of a superstring of y . An integer array LSLS is the minimal left-seed (resp. maximal left-seed) array of y , if LS[i]LS[i] is the minimal (resp. maximal) length of left seeds of y[0..i]y[0..i]. The minimal right-seed (resp. maximal right-seed) array RSRS of y is defined in a similar fashion.In this article, we present linear-time algorithms for computing all left and right seeds of y, a linear-time algorithm for computing the minimal left-seed array of y, a linear-time solution for computing the maximal left-seed array of y , an O(nlogn)-time algorithm for computing the minimal right-seed array of y, and a linear-time solution for computing the maximal right-seed array of y. All algorithms use linear auxiliary space.
Journal: Journal of Discrete Algorithms - Volume 17, December 2012, Pages 31–44