Efficient algorithms for shortest partial seeds in words

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

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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, introduced recently in the context of α-partial covers (Kociumaka et al, CPM 2013); 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 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 - 25th Annual Symposium, CPM 2014, Proceedings
PublisherSpringer Verlag
Pages192-201
Number of pages10
ISBN (Print)9783319075655
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 - Moscow, Russian Federation
Duration: 16 Jun 201418 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8486 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014
CountryRussian Federation
CityMoscow
Period16/06/1418/06/14

Fingerprint

Dive into the research topics of 'Efficient algorithms for shortest partial seeds in words'. Together they form a unique fingerprint.

Cite this