Check Transcription

Explicación

Para resolver este problema, podemos usar fuerza bruta y comprobar cada longitud posible de $r_0$ . Sean $c_0$ y $c_1$ el número de ceros y unos en $s$ , respectivamente. La longitud de $r_1$ se puede determinar por $\frac{|s| - c_0 \cdot |r_0|}{c_1}$ . Si esta longitud no es un entero, entonces este $r_0$ es inválido y no hace falta comprobarlo más.

Para cada longitud posible de $r_0$ , queremos comprobar si el patrón dado en $s$ coincide con la señal recibida $t$ . Sea el hash de $r_i$ igual a $h_i$ . Precalculando las sumas de prefijos de los hashes de $t$ , podemos recorrer $s$ y comprobar para cada carácter $s_i$ en $s$ si el hash de su parte correspondiente en $t$ es igual a $h_{s_i}$ . Esta parte correspondiente en $t$ se puede localizar si usamos un puntero $t_j$ y lo incrementamos en $|r_i|$ cada vez que comprobamos un carácter de $s$ . Al final, si todos los hashes coinciden, entonces encontramos un $r_0$ posible. En caso contrario, si hay un desajuste en algún punto, podemos terminar e ir a la siguiente longitud posible de $r_0$ .

Complejidad temporal

Primero notamos que comprobar un $r_0$ posible se puede hacer en $\mathcal{O}(|s|)$ porque para cada carácter $s_i$ en $s$ , podemos obtener el hash de su subcadena correspondiente en $t$ en $\mathcal{O}(1)$ , dado un preprocesamiento $\mathcal{O}(|s|)$ para calcular las sumas de prefijos de los hashes.

Luego, determinemos el número de longitudes posibles de $r_0$ . Sin pérdida de generalidad, supongamos $c_0 \geq c_1 \implies c_0 \geq |s| / 2$ . Como $|r_0|$ y $|r_1|$ son estrictamente positivos, $|r_0|$ debe ser menor o igual que $\lfloor |t| / c_0 \rfloor$ .

Por lo tanto, la complejidad temporal total es $\mathcal{O} (|s| \cdot (|t| / c_0)) \leq \mathcal{O} (|s| \cdot |t| \cdot (2 / |s|)) = \mathcal{O} (|t|)$ .

Implementación

C++


#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;
 
/** Calculate the prefix sums of the hashes for the given string t. */
void generate_hash(string &t) {
	rolling_hash.push_back(0);
	powers.push_back(1);
	for (int i = 0; i < t.size(); i++) {
		ull current_hash = ((rolling_hash.back() * base) % m + (ull)t[i]) % m;
		rolling_hash.push_back(current_hash);
		powers.push_back(powers.back() * base % m);
	}
}
 
/** Get the hash value of the substring (a,b] */
ull get_hash(int a, int b) {
	ull previous = rolling_hash[a] * powers[b - a] % m;
	// Add m in case rolling_hash[b] < previous
	return ((m + rolling_hash[b]) - previous) % m;
}
 
int main() {
	string s, t;
	cin >> s >> t;
	generate_hash(t);
 
	int count0 = 0;
	int count1 = 0;
	for (char &c : s) {
		if (c == '0') {
			count0++;
		} else if (c == '1') {
			count1++;
		}
	}
 
	int pairs_count = 0;
	// Brute force through all possible lengths of r0
	for (int len_r0 = 1; len_r0 < t.size() / count0; len_r0++) {
		// This r0 is invalid if the length of r1 is no longer an integer
		if ((t.size() - len_r0 * count0) % count1 != 0) { continue; }
		int len_r1 = (t.size() - len_r0 * count0) / count1;
 
		int len_ri[2] = {len_r0, len_r1};
		ull hash_i[2] = {0, 0};
 
		// pointer_t points to the current position in the received signal t.
		int pointer_t = 0;
		// i points to the current position in the pattern string s.
		for (int i = 0; i < s.size(); i++) {
			int s_i = s[i] - '0';
			// If the hash for r_i is not calculated yet, we first calculate
			// this.
			if (hash_i[s_i] == 0) {
				hash_i[s_i] = get_hash(pointer_t, pointer_t + len_ri[s_i]);
			}
 
			/*
			 * Compare the hash of r_i with the current substring in t. If they
			 * are not the same, or if both hashes (and therefore both r_0 and
			 * r_1) are the same, this r_0 is invalid and we can go to the next
			 * possibility.
			 */
			if (hash_i[s_i] != get_hash(pointer_t, pointer_t + len_ri[s_i]) ||
			    hash_i[0] == hash_i[1]) {
				/*
				 * Since we add one to the counter anyway, we want to subtract
				 * one in case this r_0 does not count.
				 */
				pairs_count--;
				break;
			}
			// Move the pointer to the start of next token.
			pointer_t += len_ri[s_i];
		}
		pairs_count++;
	}
 
	cout << pairs_count << endl;
}