Check Transcription
Contest: Mail.Ru Cup 2018 Round 3
Difficulty rating: 2100
Tags: brute force, data structures, hashing, strings

One of Arkady's friends works at a huge radio telescope. A few decades ago the telescope has sent a signal $$$s$$$ towards a faraway galaxy. Recently they've received a response $$$t$$$ which they believe to be a response from aliens! The scientists now want to check if the signal $$$t$$$ is similar to $$$s$$$.

The original signal $$$s$$$ was a sequence of zeros and ones (everyone knows that binary code is the universe-wide language). The returned signal $$$t$$$, however, does not look as easy as $$$s$$$, but the scientists don't give up! They represented $$$t$$$ as a sequence of English letters and say that $$$t$$$ is similar to $$$s$$$ if you can replace all zeros in $$$s$$$ with some string $$$r_0$$$ and all ones in $$$s$$$ with some other string $$$r_1$$$ and obtain $$$t$$$. The strings $$$r_0$$$ and $$$r_1$$$ must be different and non-empty.

Please help Arkady's friend and find the number of possible replacements for zeros and ones (the number of pairs of strings $$$r_0$$$ and $$$r_1$$$) that transform $$$s$$$ to $$$t$$$.

Input format:
The first line contains a string $$$s$$$ ($$$2 \le |s| \le 10^5$$$) consisting of zeros and ones — the original signal.

The second line contains a string $$$t$$$ ($$$1 \le |t| \le 10^6$$$) consisting of lowercase English letters only — the received signal.

It is guaranteed, that the string $$$s$$$ contains at least one '0' and at least one '1'.

Output format:
Print a single integer — the number of pairs of strings $$$r_0$$$ and $$$r_1$$$ that transform $$$s$$$ to $$$t$$$.

In case there are no such pairs, print $$$0$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, the possible pairs $$$(r_0, r_1)$$$ are as follows:

- "a", "aaaaa"
- "aa", "aaaa"
- "aaaa", "aa"
- "aaaaa", "a"

The pair "aaa", "aaa" is not allowed, since $$$r_0$$$ and $$$r_1$$$ must be different.

In the second example, the following pairs are possible:

- "ko", "kokotlin"
- "koko", "tlin"

Example input:
01
aaaaaa

Example output:
4

Example input:
001
kokokokotlin

Example output:
2

Editorial:
The solution builds on one key observation.
Suppose we know the length of $$$r_0$$$. Then, since the number of '0' and '1' is fixed and the length of the resulting string is also fixed, we know the length of $$$r_1$$$ (or know, that there is no integer-sized $$$r_1$$$ possible).
So let's bruteforce the length of $$$r_0$$$, calculate the length of $$$r_1$$$ and then check whether the corresponding substrings of $$$t$$$ are equal (so $$$r_0$$$ and $$$r_1$$$ can be defined correctly).
Sounds like $$$O(|s| |t|)$$$ (since the number of candidates is $$$\le |t|$$$ and check can be done in $$$|s|$$$, for example with hashes)? Haha, it is $$$O(|t|)$$$.
First, notice that it is not exactly important whether we bruteforce length of $$$r_0$$$ or $$$r_1$$$ — one of them defines the other one.
So suppose we are bruteforcing over the letter with larger number of occurrences in pattern string $$$s$$$.
Let's denote it's number of occurrences as $$$c$$$, this way, clearly, there are at most $$$\frac{|t|}{c}$$$ candidates. And each candidate is checked in $$$|s|$$$. So the whole time is $$$\frac{|t|}{c} |s|$$$
Since we used the more frequent letter, $$$c \ge \frac{|s|}{2}$$$. And hence $$$\frac{|t|}{c} |s| \le 2|t|$$$.