TY - GEN
T1 - Fast algorithm for partial covers in words
AU - Kociumaka, Tomasz
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Waleń, Tomasz
PY - 2013/9/24
Y1 - 2013/9/24
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 word w covered by u thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of u. In this article we introduce a new notion of partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least a given number of positions in w. Our main result is an O(nlogn)-time algorithm for computing the shortest partial covers of a word of length n.
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 word w covered by u thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of u. In this article we introduce a new notion of partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least a given number of positions in w. Our main result is an O(nlogn)-time algorithm for computing the shortest partial covers of a word of length n.
UR - http://www.scopus.com/inward/record.url?scp=84884295653&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884295653&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38905-4_18
DO - 10.1007/978-3-642-38905-4_18
M3 - Conference contribution
AN - SCOPUS:84884295653
SN - 9783642389047
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 177
EP - 188
BT - Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
T2 - 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
Y2 - 17 June 2013 through 19 June 2013
ER -