消除子串

题目描述

给定两个字符串 $p$ 和 $t$，从 $t$ 的第一个字符开始扫描，若发现 $t$ 中含有 $p$ 的子串，则将这个子串完整地删除。不断进行这个操作，直到 $t$ 中不含 $p$ 为止。请输出最后留下的 $t$。

输入格式

• 第一行：单个字符串表示 $p$
• 第二行：单个字符串表示 $t$
• 保证 $p$ 与 $t$ 仅由小写字母构成。

输出格式

• 单个字符串表示答案，保证最后答案不会是空串。

数据范围

• 对于 $30\%$ 的数据，$1 \leq |t| \leq 100$
• 对于 $60\%$ 的数据，$1 \leq |t| \leq 10000$
• 对于 $100\%$ 的数据，$1 \leq |p| \leq |t| \leq 3,000,000$

样例数据

输入:

ba
ababbaac

输出:

ac

解释: 开始时 $t$ 是 "ababbaac"，发现 "ba" 子串后删除第一次得到 "ababac"，再次删除得到 "ac"。此时没有更多的 "ba" 子串，所以程序结束。