Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings.

This may be interpreted as finding the maximum window size $k$ such that for each column $(a, b, c)$ across the three strings, it holds that $a \lor b \lor c$ is true. If we instead require $a = b = c$, then we recover the original longest common substring (LCS) problem, for which there is a linear time algorithm using suffix arrays. Can a similar linear time result be achieved here?

example problem instance

  • 1
    $\begingroup$ I don’t see how to get linear time even for 2 strings. The only efficient thing I can think of is FFT, since it allows one to “find X for all possible shifts of two arrays”. $\endgroup$
    – user114966
    Feb 16, 2021 at 19:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.