【CF】1056E-Check Transcription 题解

传送门：1056E
标签：思维

题目大意

阿卡迪的朋友在一家大型射电望远镜工作。几十年前，该望远镜向遥远星系发送了一个信号 $s$。
最近他们收到了回复 $t$，他们认为这是外星人的回应！科学家们现在想要检查信号 $t$ 是否与 $s$ 类似。原始信号 $s$ 是零和一的序列（每个人都知道二进制代码是宇宙通用语言）。返回的信号 $t$ 看起来不像 $s$ 那么简单，但科学家们不会放弃！他们将 $t$ 表示为英文字母的序列，并表示 $t$ 与 $s$ 类似，如果你能用某个字符串 $r_0$ 替换 $s$ 中的所有零，用另一个字符串 $r_1$ 替换 $s$ 中的所有一，并获得 $t$。字符串 $r_0$ 和 $r_1$ 必须不同且非空。请帮助阿卡迪的朋友找到零和一的可能替换数（$r_0$ 和 $r_1$ 的配对数），将 $s$ 转换为 $t$。
输入：第一行包含一个字符串 $s$（$2\le |s|\le 10^5$），由零和一组成 — 原始信号。第二行包含一个仅由小写英文字母组成的字符串 $t$（$1\le |t|\le 10^6$） — 收到的信号。保证 $s$ 包含至少一个 ‘0’ 和至少一个 ‘1’。
输出：打印一个整数——将 $s$ 转换为 $t$ 的 $r_0$ 和 $r_1$ 的配对数。如果没有这样的配对，则打印 0。

算法分析

• 这题要靠观察得出结论。假设我们知道 $r_0$ 的长度。由于 ‘0’ 和 ‘1’ 的数量固定并且结果字符串的长度也是固定的，我们知道 $r_1$ 的长度（或者知道没有合适的整数大小的 $r_1$ 存在）。此时我们可以暴力求出 $r_0$ 的长度，计算 $r_1$ 的长度，然后检查相应的子串是否相等（所以 $r_0$ 和 $r_1$ 可以正确地定义）。
• 听起来像是 $O(|s||t|)$（候选数少于 $|t|$，检查可以在 $|s|$ 内完成，例如使用哈希表）？并非，实际上是 $O(|t|)$。首先，注意到我们暴力求解哪个字母并不重要 — 它们中的一个会定义另一个。所以假设我们在暴力求解模式字符串 $s$ 中出现次数较多的字母。
• 我们将它的出现次数记为 $c$，这样显然有至多 $\frac{|t|}{c}$ 个候选。每个候选都在 $|s|$ 内检查。所以总时间是 $\frac{|t|}{c}|s|$因为我们使用了更频繁的字母，$c\ge \frac{|s|}{2}$. 因此 $\frac{|t|}{c}|s|\le 2|t|$

代码实现

#include <bits/stdc++.h>
using namespace std;

int n, m;
string s, t;
const int P = 131;
long long L[1000100], H[1000100], tx, ty;
const int mod = 1e9 + 7;
int x, y;

int main(){
	cin >> s >> t;
	n = t.length();
	m = s.length();
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '0') x++;
		else y++;
	}
	H[0] = 1;
	for(int i = 1; i <= n; i++){
		L[i] = (L[i - 1] * P % mod + t[i - 1])%mod;
		H[i] = H[i - 1] * P % mod;
	}
	int ans = 0;
	for(int i = 1; i * x + y <= n; i++){
		if((n - i * x) % y != 0) continue;
		int j = (n - i * x) / y;
		int l = 0;
		bool flag = true, f1 = false, f2 = false;
		for(int k = 0; k < m; k++){
			if(s[k] == '0'){
				if(i + l > n){
					flag = false;
					break;
				}
				if(f1 == false) tx = ((L[i + l] - L[l] * H[i]) % mod + mod) % mod;
				else if(tx !=  ((L[i + l] - L[l] * H[i]) % mod + mod) % mod){
					flag = false;
					break;
				} 
				f1 = true;
				l += i;
			}else{
				if(j + l > n){
					flag = false;
					break;
				}
				if(f2 == false) ty = (L[j + l] - L[l] * H[j] % mod + mod) % mod;
				else if(ty != (L[j + l] - L[l] * H[j] % mod + mod) % mod){
					flag = false;
					break;
				} 
				f2 = true;
				l += j;
			}
		}
		if(flag && tx != ty) ans++;
	}
	cout << ans << '\n';
	return 0;
}