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.