← 返回题目列表

Codeforces · 625/B

B. 企业之战

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

很久以前,在遥远的银河系中,菠萝和果戈里两家IT巨头继续展开激烈的竞争。关键时刻即将到来:果戈理准备发布其新款平板电脑 Lastus 3000。

这款新设备配备了专门设计的人工智能 (AI)。 Pineapple 的员工竭尽全力尽可能推迟 Lastus 3000 的发布。最后,他们发现,这种新型人工智能的名字与200年前菠萝发布的手机的名字很相似。由于其名称的所有权利都属于“菠萝”,因此他们主张更改果戈里人工智能的名称。

Pineapple 坚称,他们的手机名称以 AI 名称的子字符串形式出现。由于技术名称已经印在所有设备上,果戈里导演决定将AI名称中的一些字符替换为“#”。由于此操作相当昂贵,因此您应该找到用“#”替换的最少字符数,这样 AI 的名称不包含手机名称作为子字符串。

子串是字符串的连续子序列。

输入

输入的第一行包含Gogol设计的AI的名称,其长度不超过100 000个字符。第二行包含Pineapple 200年前发布的手机名称,长度不超过30。两个字符串都非空且仅由小英文字母组成。

输出

打印必须用“#”替换的最少字符数,以获得手机名称不会作为子字符串出现在 AI 名称中。

示例

输入 #1

intellect
tell

输出 #1

1

输入 #2

google
apple

输出 #2

0

输入 #3

sirisiri
sir

输出 #3

2

注意

在第一个示例中,AI 的名称可能会替换为“int#llect”。

在第二个示例中,果戈理可以保持事物原样。

在第三个示例中,AI 的新可能名称之一可能是“s#ris#ri”。