题目描述

给定一个字符串 $p$ 为模式，再给定一个字符串 $t$ 作为文本，请计算 $t$ 中至少需要删除多少个字符，才能避免 $p$ 作为一个子串出现在文本 $t$ 中。

输入格式

第一行：单个字符串 $p$，保证全部由小写拉丁字母构成； 第二行：单个字符串 $t$，保证全部由小写拉丁字母构成；

输出格式

单个整数：表示问题的答案。

aba
ababaa

1

样例解释 1

删a变成abbaa

baa
baaaaaaa

1

样例解释 2

删除第一个b

数据范围

设 $n$ 表示文本字符串的长度，$m$ 表示模式字符串的长度，则有

• 对于 $30\%$ 的数据， $1\leq n\leq 20$，$1\leq m\leq 10$
• 对于 $60\%$ 的数据， $1\leq n\leq 200$，$1\leq m\leq 100$
• 对于 $100\%$ 的数据， $1\leq n\leq 10000$，$1\leq m\leq 5000$。