Efficient Algorithms for Shortest Partial Seeds in Words

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

2 Citations (Scopus)


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, introduced recently in the context of α-partial covers (Kociumaka et al, CPM 2013); an O(nlogn)-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 an algorithm for computing shortest α-partial seeds that works in O(n) time if the Cover Suffix Tree is already given.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings
EditorsAlexanderS. Kulikov, SergeiO. Kuznetsov, Pavel Pevzner
PublisherSpringer International Publishing
Number of pages10
ISBN (Electronic)978-3-319-07566-2
ISBN (Print)978-3-319-07565-5
Publication statusPublished - 2014
Event25th Annual Symposium, CPM 2014 - Moscow, Russian Federation
Duration: 16 Jun 201418 Jun 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
ISSN (Print)0302-9743


Conference25th Annual Symposium, CPM 2014
Country/TerritoryRussian Federation


Dive into the research topics of 'Efficient Algorithms for Shortest Partial Seeds in Words'. Together they form a unique fingerprint.

Cite this