TY - GEN
T1 - Efficient algorithms for shortest partial seeds in words
AU - Kociumaka, Tomasz
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Waleń, Tomasz
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84958542977&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958542977&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-07566-2_20
DO - 10.1007/978-3-319-07566-2_20
M3 - Conference contribution
AN - SCOPUS:84958542977
SN - 9783319075655
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 201
BT - Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings
PB - Springer Verlag
T2 - 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014
Y2 - 16 June 2014 through 18 June 2014
ER -