CF1056E Check Transcription 题解

题意：

cxy 在一座巨大的射电望远镜工作。几十年前，该望远镜向一个遥远的星系发送了一个信号 $s$ 。最近，她收到了一个回应 $t$ ，她认为这是外星人的回应！科学家们现在想要检查信号 $t$ 是否与 $s$ 相似。原始信号 $s$ 是由 0 和 1 组成的序列（大家都知道二进制是宇宙通用语言）。然而，返回的信号 $t$ 看起来并不像 $s$ 那样简单，但是科学家们并没有放弃！她将 $t$ 表示为一个英文字母的序列，并且说如果你可以用某个字符串 $r_0$ 替换 $s$ 中的所有零，并用另一个字符串 $r_1$ 替换 $s$ 中的所有一，得到 $t$，那么 $t$ 就与 $s$ 相似。字符串 $r_0$ 和 $r_1$ 必须是不同且非空的。

请帮助 cxy ，找出将 $s$ 转换为 $t$ 的可能的零和一的替换次数（字符串 $r_0$ 和 $r_1$ 的对数）。

输入格式：

第一行包含一个由零和一组成的字符串 $s\left(2 \leq|s| \leq 10^5\right)$ - 原始信号。第二行包含一个只包含小写英文字母的字符串 $t\left(1 \leq|t| \leq 10^6\right)$ - 接收到的信号。保证字符串 $s$ 至少包含一个 0 和一个 1 。

输出格式：

输出一个整数：将 $s$ 转换为 $t$ 的字符串对 $r_0$ 和 $r_1$ 的数量。如果没有这样的字符串对，则输出 0。

注：本题解中的 $s,t$ 与原题中相反，请勿混淆。

不妨设 $t_0 = \mathtt{0}$ ，否则我们可以把 0,1 互换，不会改变原串性质。

由于 $t_0$ 对应的一定是 $s$ 的一个前缀，所以我们可以枚举这个串，并且可以直接计算出 $\mathtt{1}$ 对应的串长。

这样我们就可以很方便地用字符串哈希在 $\mathcal{O}(|t|)$ 的时间内检验是否合法了。

这个算法看上去是 $\mathcal{O}(|s|\cdot|t|)$ 的，但是因为 0,1 中一定有一个出现次数 $\ge \dfrac{|t|}{2}$ ，这会限制对应的串长。

因此时间复杂度为 $\mathcal{O}\left(\dfrac{|s|}{|t|}\cdot |t|\right) = \mathcal{O}(|s|)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
const int hash_base[2] = {13, 7};
const int hash_mod[2] = {1000000009, 998244853};

char s[N],t[N],vis[2];
int n,m,res,f[2][2],len[2],hsh[2][N],pwd[2][N];
void init()
{
    for(int c = 0; c < 2; c++)
    {
        int base = hash_base[c], mod = hash_mod[c];
        hsh[c][0] = pwd[c][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            pwd[c][i] = pwd[c][i - 1] * base % mod;
            hsh[c][i] = (hsh[c][i - 1] + s[i]) * base % mod;
        }
    }
}
pii query(int l,int r)
{
    return {
        (hsh[0][r] - hsh[0][l - 1] * pwd[0][r - l + 1] % hash_mod[0] + hash_mod[0]) % hash_mod[0],
        (hsh[1][r] - hsh[1][l - 1] * pwd[1][r - l + 1] % hash_mod[1] + hash_mod[1]) % hash_mod[1]
    };
}
bool check()
{
    vis[0] = vis[1] = 0; memset(f, 0, sizeof(f)); int it = 1;
    for(int i = 1; i <= m; i++)
    {
        const bool x = t[i] ^ 48; pii cxy = query(it, it + len[x] - 1);
        if(!vis[x]) { vis[x] = true; f[x][0] = cxy.first, f[x][1] = cxy.second; }
        else if(cxy.first != f[x][0] || cxy.second != f[x][1]) return false;
        it += len[x];
    }
    return !(f[0][0] == f[1][0] && f[0][1] == f[1][1]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (t + 1) >> (s + 1); m = strlen(t + 1); n = strlen(s + 1);
    init(); int c[2] = {0, 0}; for(int i = 1; i <= m; i++) ++c[t[i] ^ 48];
    if(c[0] < c[1]) { swap(c[0], c[1]); for(int i = 1; i <= m; i++) t[i] ^= 1; }
    for(int k = 1; k <= n / c[0]; k++)
    {
        len[0] = k; if((n - k * c[0]) % c[1]) continue;
        len[1] = (n - k * c[0]) / c[1]; if(len[1] == 0) continue;
        res += check();
    }
    cout << res << '\n';
    return 0;
}