# Additional Problem 11: 2-Anticovers (Preliminary version)

The 2-anticover of a string $x$ is a set of pairwise distinct fragments of $x$ of length 2, covering $x$.

Design a linear algorithm testing if the string $w$ has a 2-anticover. Assume integer alphabet (sortable in linear time).

Use linear time algorithm for the satisfability of 2CNF formulas (CNF = ''conjuntive normal form''). In this problem we have a Boolean formula which is a conjunction of two variables clauses (alternatives). Example of a 2CNF formula is: $(x_2\lor x_4) \land (x_1 \lor \lnot x_3)$.

## References

• M. Alzamel, A. Conte, S. Denzumi, R. Grossi, C. S. Iliopoulos, K. Kurita, and K. Wasa, Finding the anticover of a string, In I. L. Gørtz and O.Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, volume 161 of LIPIcs, pages 2:1-2:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.