CLR cover
Previous problem

Problem 136: 2-anticovers

Next problem

A 2-anticover of a word $x$ is a set of pairwise distinct factors of $x$ of length 2 that cover the whole word. The notion is dual of the notion of a cover, for which a unique factor (or a finite number of them) covers the whole word. The duality is similar to that of powers and antipowers, where the word is a concatenation of the same factor or of distinct factors. Instead, for anticovers or covers the occurrences factors can overlap or just be adjacent.

The notion generalises obviously to $k$-anticover.

On an alphabet of size $\sigma$, since the number of words of length $k$ is $\sigma^k$, no word of length larger than $k\sigma^k$ admits a $k$-anticover. This is why it is appropriate to consider an integer alphabet that is potentially infinite.

Design a linear algorithm testing if the word $x$ admits a 2-anticover, assume its alphabet is sortable in linear time (integer alphabet).

Use a linear-time algorithm for the satisfiability of 2CNF formulas (CNF = conjunctive normal form). Each 2CNF formula is a conjunction of two variables "clauses" (alternatives of variables and their negations). An example of a 2CNF formula is: $(x_2\lor x_4) \land (x_1 \lor \lnot x_3)$.

References