题目描述

给你一个长度为 $n$ 的字符串 $A$，再给你一个长度为 $m$ 的字符串 $B$，求至少在 $A$ 中删去多少个字符才能使得 $B$ 不是 $A$ 的子串。注：该题只读入 $A$ 和 $B$，不读入长度，先读入 $A$，再读入 $B$。数据保证 $A$ 和 $B$ 中只含小写字母。

输入格式

第一行读入一个字符串，表示 $A$，第二行读入一个字符串，表示 $B$。

输出格式

一行，一个整数，表示要删去的最短长度。

ababaa
aba

1

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 10^3$，$m\le n$。