10
$\begingroup$

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the pattern and other in our sequence).

The goal is to minimize the number of ones in the sequence.

For example let p = 101,then our sequence might be 0011001100...

if we set p = 1011 then out sequence might be 000110001100011

For small patterns it's quite easy to prove that these are the optimal sequences, but I couldn't generalize anything for more complex patterns.

This looks like a known problem but I wasn't able to find anything about it. I think it is a special version of a set cover problem which is NP hard (for patterns with only 2 ones it can even be turned into edge cover) - interpret every placement of pattern as element of a set S and every position in our sequence as subset of S which only contains placements of p that contain that position. Then let U be the family of those subsets. Problem is to cover S using the least possible subsets from U. Although this might be over-generalization because in our problem every subset is of the same size.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The problem can be solved in time $O(2^{|p|} n^2)$ using dynamic programming. Construct a DFA of size $O(2^{|p|})$ accepting valid strings. Then compute, for each $w \leq m \leq n$, whether there exists a valid word of length $m$ and weight $w$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was kind of hoping for something more efficient, but thank for the answer. Have you maybe managed to reduce the problem to something that is NP hard? $\endgroup$ Commented Aug 9, 2024 at 15:08

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.