King's College London

Research portal

Efficient algorithms for shortest partial seeds in words

Research output: Contribution to journalArticlepeer-review

Tomasz Kociumaka, Solon Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Original languageEnglish
JournalTheoretical Computer Science
E-pub ahead of print30 Nov 2016


King's Authors


Abstract A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al., 2015, [13]); an O ( n log ⁡ n ) -time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O ( n ) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454