1877:秘密串

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:2 解决:2

题目描述

课堂上,蒜头君写出一个只包含小写字母的集合 S,并且告诉同学们 S 中的每个字母都是秘密字母,因为它包含一个秘密。如果一个字符串内包含 S 中所有的秘密字母,则这个字母为秘密串(可以包含非秘密字母),秘密串内秘密字母的种类越多,则包含的秘密越重要。

给你一个只包含小写字母的集合 S 和一个只包含小写字母的字符串 str。现在你需要在 str 中找到一个最短的子串(秘密串),使得该子串包含 S 中所有的字母,请你输出该子串的长度。

细节补充:

  1. 子串:字符串中任意个连续的字符组成的子序列
  2. 小写字母集合 S 内只包含若干个互不相同的小写字母,且至少包含一个小写字母,最多包含 26 个小写字母。

输入

第一行,输入一个只包含小写字母的字符串 S,表示小写字母集合。

第二行,输入一个由小写字母组成的字符串 str

保证 $1\le len_s \le 26, len_s \le len_{str}\le 10000$

数据保证 str 内一定包含 S 内所有的字母。

输出

输出一个整数,表示最短秘密串的长度。

样例输入-1 复制

jsk
hellojisuanke

样例输出-1 复制

7

样例输入-2 复制

jsk
jisuanskejuck

样例输出-2 复制

4

提示

样例解释1:子串 ”jisuank" 包含 S 中所有字符,且为最短的秘密串

样例解释2:可以找到两个较短的秘密串:

  • "jisuansk",长度为 8
  • "skej",长度为 4
可以对上述两个子串向外拓展,同样可以得到秘密串,但是长度为增加,所以最短的秘密串长度为 4