CF625B War of the Corporations

很久以前，在一个遥远的星系中，两家巨大的 IT 公司——Pineapple 和 Gogol——继续着激烈的竞争。关键时刻即将到来：Gogol 准备发布他们的新平板 Lastus 3000。 这款新设备配备了专门设计的人工智能（AI）。Pineapple 的员工竭尽全力，只为尽量推迟 Lastus 3000 的发布。最终，他们发现，这个人工智能的名字与 Pineapple 200 年前发布的一款手机的名字很相似。由于该手机名称的所有权属于 Pineapple，他们坚持要求 Gogol 更改其人工智能的名称。 Pineapple 坚称他们手机名称在 AI 的名称中作为子串出现。由于技术名称已经被印在所有设备上，Gogol 的总裁决定将 AI 名称中的某些字符替换为 “\#”。由于这个操作极其昂贵，你需要找出最少需要替换多少个字符为 “\#”，才能使 AI 的名称中不再包含手机名称作为子串。 子串指的是字符串的一个连续子序列。

输入的第一行包含 Gogol 设计的 AI 名称，长度不超过 $100000$ 个字符。第二行包含 Pineapple 200 年前发布的手机名称，长度不超过 $30$。两个字符串均非空，且只包含小写英文字母。

输出最少需要将多少个字符替换成 “\#”，才能保证在 AI 名称中不再出现手机名称作为子串。

在第一个样例中，AI 的名称可以被替换为 “int#llect”。 在第二个样例中，Gogol 可以保持名称不变。 在第三个样例中，AI 的新名称可以为 “s#ris#ri”。 由 ChatGPT 5 翻译