1 Citation (Scopus)


A k-anticover of a string x is a set of pairwise distinct factors of x of equal length k, such that every symbol of x is contained into an occurrence of at least one of those factors. The existence of a k-anticover can be seen as a notion of non-redundancy, which has application in computational biology, where they are associated with various non-regulatory mechanisms. In this paper we address the complexity of the problem of finding a k-anticover of a string x if it exists, showing that the decision problem is NP-complete on general strings for k-3. We also show that the problem admits a polynomial-time solution for k = 2. For unbounded k, we provide an exact exponential algorithm to find a k-anticover of a string of length n (or determine that none exists), which runs in O(min{3 n-k 3 , ( k(k+1) 2 ) n k+1 }) time using polynomial space. 2012 ACM Subject Classification Mathematics of computing ! Combinatorics on words.

Original languageEnglish
Title of host publication31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
EditorsInge Li Gortz, Oren Weimann
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771498
Publication statusPublished - 1 Jun 2020
Event31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 - Copenhagen, Denmark
Duration: 17 Jun 202019 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020


  • Anticover
  • Np-complete
  • String algorithms
  • Stringology


Dive into the research topics of 'Finding the Anticover of a String'. Together they form a unique fingerprint.

Cite this