传送门
暴力枚举\(0\)的长度，如果对应的\(1\)的长度也是一个整数就去check是否合法。check使用字符串哈希。
复杂度看起来是\(O(st)\)的，但是因为\(01\)两个数中数量较多的至少有\(\frac{|s|}{2}\)个，那么最多有\(\frac{2|t|}{|s|}\)个可能的答案，而每一次check是\(O(|s|)\)的，所以总复杂度是\(O(|t|)\)的
#include<bits/stdc++.h>
#define ll long long
#define PLL pair < ll , ll >
//This code is written by Itst
using namespace std;inline int read(){int a = 0;char c = getchar();bool f = 0;while(!isdigit(c) && c != EOF){if(c == '-')f = 1;c = getchar();}if(c == EOF)exit(0);while(isdigit(c)){a = (a << 3) + (a << 1) + (c ^ '0');c = getchar();}return f ? -a : a;
}const int seed = 13331 , MOD1 = 1e9 + 7 , MOD2 = 1e9 + 9;
char s1[100010] , s2[1000010];
int L1 , L2 , cnt0 , cnt1 , cnt;
ll Hash[1000010][2] , poww[1000010][2];void input(){scanf("%s %s" , s1 + 1 , s2 + 1);L1 = strlen(s1 + 1);L2 = strlen(s2 + 1);
}void init(){for(int i = 1 ; i <= L1 ; ++i)s1[i] == '0' ? ++cnt0 : ++cnt1;poww[0][0] = poww[0][1] = 1;for(int i = 1 ; i <= L2 ; ++i){Hash[i][0] = (Hash[i - 1][0] * seed + s2[i]) % MOD1;Hash[i][1] = (Hash[i - 1][1] * seed + s2[i]) % MOD2;poww[i][0] = poww[i - 1][0] * seed % MOD1;poww[i][1] = poww[i - 1][1] * seed % MOD2;}
}inline PLL calcHash(int i , int j){return PLL((Hash[i + j - 1][0] - Hash[i - 1][0] * poww[j][0] % MOD1 + MOD1) % MOD1 , (Hash[i + j - 1][1] - Hash[i - 1][1] * poww[j][1] % MOD2 + MOD2) % MOD2);
}void work(){for(int i = 1 ; i * cnt0 < L2 ; ++i)if(!((L2 - i * cnt0) % cnt1)){int p = 1 , j = (L2 - i * cnt0) / cnt1;bool f = 1;PLL Hash0 = PLL(-1,0) , Hash1 = PLL(-1,0);for(int k = 1 ; f && k <= L1 ; ++k)if(s1[k] == '0'){if(Hash0.first == -1)Hash0 = calcHash(p , i);elseif(Hash0 != calcHash(p , i))f = 0;p += i;}else{if(Hash1.first == -1)Hash1 = calcHash(p , j);elseif(Hash1 != calcHash(p , j))f = 0;p += j;}cnt += f && (Hash0 != Hash1);}
}void output(){cout << cnt;
}int main(){
#ifndef ONLINE_JUDGEfreopen("in" , "r" , stdin);//freopen("out" , "w" , stdout);
#endifinput();init();work();output();return 0;
}
