Official Editorial

Explanation

To solve this problem, we can use brute force and check every possible length of $r_0$. Let $c_0$ and $c_1$ denote the number of zeros and ones in $s$, respectively. The length of $r_1$ can be determined by $\frac{|s| - c_0 \cdot |r_0|}{c_1}$. If this length is not an integer, then this $r_0$ is invalid and no further check is required for it.

For each possible length of $r_0$, we want to check if the given pattern in $s$ matches the received signal $t$. Let the hash of $r_i$ be $h_i$. By pre-calculating the prefix sums of the hashes for $t$, we can iterate through $s$ and check for each character $s_i$ in $s$ if the hash of its corresponding part in $t$ equals $h_{s_i}$. This corresponding part in $t$ can be located if we use a pointer $t_j$ and increase it by $|r_i|$ every time we checked a character from $s$. At the end, if all hashes match, then we have found a possible $r_0$. Otherwise, if there is a mismatch at any point, we can terminate and go for the next possible length of $r_0$.

Time Complexity

We first note that checking for a possible $r_0$ can be done in $\mathcal{O}(|s|)$ since for each character $s_i$ in $s$, we can get the hash of its corresponding substring in $t$ in $\mathcal{O}(1)$, given $\mathcal{O}(|s|)$ pre-processing to calculate the prefix sums of the hashes.

Then, let's determine that number of possible lengths of $r_0$. Without loss of generality, suppose $c_0 \geq c_1 \implies c_0 \geq |s| / 2$. As $|r_0|$ and $|r_1|$ are strict positive, $|r_0|$ must be less or equal to $\lfloor |t| / c_0 \rfloor$.

Therefore, the overall time complexity is $\mathcal{O} (|s| \cdot (|t| / c_0)) \leq \mathcal{O} (|s| \cdot |t| \cdot (2 / |s|)) = \mathcal{O} (|t|)$.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long int;

ull m = 1e9 + 9;
ull base = 9973;
// Hashes and powers start with 1
vector<ull> rolling_hash;
vector<ull> powers;