Fast Algorithm for Partial Covers in Words

DOI10.1007/978-3-642-38905-4_18MaRDI QIDQ4928571zbMATH OpenOpenAlexFDO

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

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0163

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

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 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 $alpha$-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least $alpha$ positions in $w$. We develop a data structure of $O(n)$ size (where $n=|w|$) that can be constructed in $O(nlogn)$ time which we apply to compute all shortest $alpha$-partial covers for a given $alpha$. We also employ it for an $O(nlogn)$-time algorithm computing a shortest $alpha$-partial cover for each $alpha=1,2,ldots,n$.

Recommendations

• Fast algorithm for partial covers in words
• Algorithmic combinatorics on partial words
• Efficient algorithms for shortest partial seeds in words
• Efficient Algorithms for Shortest Partial Seeds in Words
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• A work-time optimal algorithm for computing all string covers

Cited in

(8)

• Efficient algorithms for shortest partial seeds in words
• Approximate cover of strings
• Can we recover the cover?
• Computing all repeats of a partial word
• Fast algorithm for partial covers in words
• Quasi-periodicity under mismatch errors
• Efficient Algorithms for Shortest Partial Seeds in Words
• Shortest covers of all cyclic shifts of a string

This page was built for publication: Fast Algorithm for Partial Covers in Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928571)