← 返回题目列表

Codeforces · 1056/E

E. 检查转录

中文机器翻译题面 查看原题

阿尔卡迪的一位朋友在一台巨大的射电望远镜前工作。几十年前,望远镜向一个遥远的星系发送了一个信号$$$s$$$。最近他们收到了回复$$$t$$$,他们认为这是来自外星人的回复!科学家们现在想要检查信号 $$$t$$$ 是否与 $$$s$$$ 相似。

原始信号 $$$s$$$ 是一个由 0 和 1 组成的序列(每个人都知道二进制代码是宇宙范围内的语言)。然而,返回的信号$$$t$$$看起来并不像$$$s$$$那么容易,但科学家们并没有放弃!他们将 $$$t$$$ 表示为英文字母序列,并表示 $$$t$$$ 与 $$$s$$$ 类似,如果你可以用某个字符串 $$$r_0$$$ 替换 $$$s$$$ 中的所有零,并用其他字符串 $$$r_1$$$ 替换 $$$s$$$ 中的所有零,并获得 $$$t$$$。字符串 $$$r_0$$$ 和 $$$r_1$$$ 必须不同且非空。

请帮助 Arkady 的朋友找出将 $$$s$$$ 转换为 $$$t$$$ 的 0 和 1 的可能替换数量(字符串 $$$r_0$$$ 和 $$$r_1$$$ 的对数)。

输入

第一行包含一个由零和一组成的字符串 $$$s$$$ ($$$2 \le |s| \le 10^5$$$) — 原始信号。

第二行包含一个仅由小写英文字母组成的字符串 $$$t$$$ ($$$1 \le |t| \le 10^6$$$) — 接收到的信号。

保证字符串 $$$s$$$ 包含至少一个“0”和至少一个“1”。

输出

打印单个整数 - 将 $$$s$$$ 转换为 $$$t$$$ 的字符串对 $$$r_0$$$ 和 $$$r_1$$$ 的数量。

如果没有这样的对,则打印 $$$0$$$。

示例

输入 #1

01
aaaaaa

输出 #1

4

输入 #2

001
kokokokotlin

输出 #2

2

注意

在第一个示例中,可能的对 $$$(r_0, r_1)$$$ 如下:

- “一个”,“aaaaa”
- “aa”,“aaaa”
- “aaaa”,“aa”
- “aaaaa”,“a”

不允许使用“aaa”、“aaa”对,因为 $$$r_0$$$ 和 $$$r_1$$$ 必须不同。

在第二个示例中,可能有以下对:

- “ko”,“kokotlin”
- “科科”,“特林”