1877:秘密串
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:2
解决:2
题目描述
课堂上,蒜头君写出一个只包含小写字母的集合 S,并且告诉同学们 S 中的每个字母都是秘密字母,因为它包含一个秘密。如果一个字符串内包含 S 中所有的秘密字母,则这个字母为秘密串(可以包含非秘密字母),秘密串内秘密字母的种类越多,则包含的秘密越重要。
给你一个只包含小写字母的集合 S 和一个只包含小写字母的字符串 str。现在你需要在 str 中找到一个最短的子串(秘密串),使得该子串包含 S 中所有的字母,请你输出该子串的长度。
细节补充:
- 子串:字符串中任意个连续的字符组成的子序列
- 小写字母集合 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