题解【CF1056E Check Transcription】

· · 题解

提供一种实现简单的 \mathcal{O}(|s|) 做法（这个 |s| 是翻译中那个 10^6 范围的东西）。

思路

首先我们不难发现， t 串的开头那个字符一定对应的是 s 串的一个前缀。因此我们只需要枚举这个字符对应串的长度就可以唯一确定它对应的串。

然后我们注意到 t 串中 0/1 的出现次数我们都可以知道，我们又知道了某个字符的长度，那么另一个字符对应串的长度我们也能确定。

考虑我们扫一遍 t 串，由于每一个字符对应的字符串长度我们都已知，因此若我们 \mathcal{O}(|t|) 扫一遍 t 串，就可以求出每一个字符在 s 串中对应的 起始位置。

再加上我们确定的长度，每一个字符在 s 中对应的串我们可以通过哈希 \mathcal{O}(1) 求得，因此我们得到了一个 \mathcal{O}(|t|) 判断一组长度是否合法的算法。

但是这样看起来还是 \mathcal{O}(|s||t|) 的，不过注意到在 t 串中，出现次数更多的那一个字符的出现次数一定 \ge \frac{|t|}{2}。

因此我们枚举这一个字符，显然另一个字符的长度还是可以 \mathcal{O}(1) 求，而且我们枚举的上界只需要达到 \mathcal{O}(\frac{|s|}{|t|})。

因此最终复杂度分析出来是 \mathcal{O}(\frac{|s|}{|t|})\times\mathcal{O}(|t|)=\mathcal{O}(|s|) 的。

代码

只放关键部分

const int MAXN = 1e6 + 5;
char t[MAXN], s[MAXN];
int m, n;

int h[MAXN][2], b[MAXN][2];
const int MOD[2] = {114, 1919};
const int base[2] = {514, 810};

inline void init() {    
    b[0][0] = b[0][1] = 1; rep(i, 1, n) {
        b[i][0] = 1ll * b[i - 1][0] * base[0] % MOD[0];
        b[i][1] = 1ll * b[i - 1][1] * base[1] % MOD[1];

        h[i][0] = (1ll * h[i - 1][0] * base[0] + s[i]) % MOD[0];
        h[i][1] = (1ll * h[i - 1][1] * base[1] + s[i]) % MOD[1];
    }
}

int f[2][2], len[2];
bool vis[2];

inline void get_hash(int &x, int &y, int l, int r) {
    const int o = (r - l + 1);
    x = (((1ll * h[r][0] - 1ll * h[l - 1][0] * b[o][0]) % MOD[0]) + MOD[0]) % MOD[0];
    y = (((1ll * h[r][1] - 1ll * h[l - 1][1] * b[o][1]) % MOD[1]) + MOD[1]) % MOD[1];
}

inline int judge() {
    vis[0] = vis[1] = 0; memset(f, 0, sizeof(f));
    int it = 1; rep(i, 1, m) {
        const bool x = t[i] ^ 48; int u, v; get_hash(u, v, it, it + len[x] - 1);
        if(!vis[x]) { vis[x] = 1; f[x][0] = u; f[x][1] = v; }
        else if(u != f[x][0] || v != f[x][1]) return 0;
        it += len[x];
    }
    return !(f[0][0] == f[1][0] && f[0][1] == f[1][1]);
}

signed main() {
    read(t + 1); read(s + 1); m = strlen(t + 1); n = strlen(s + 1);
    init(); int c[2] = {0, 0}; rep(i, 1, m) ++ c[t[i] ^ 48];
    if(c[0] < c[1]) { std::swap(c[0], c[1]); rep(i, 1, m) t[i] ^= 1; }
    int ans = 0; rep(k, 1, n / c[0]) {
        len[0] = k; if((n - k * c[0]) % c[1]) continue;
        if(!(len[1] = (n - k * c[0]) / c[1])) continue;
        ans += judge();
    }
    print(ans);
}