CLR cover

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