#3194. 无限重复

无限重复

题目限制

1000 ms 256 M

题目描述

我们将 aazz2626 个字母的排列打乱顺序,得到一个新的字符串 ss (长度 2626 , 包括 aazz )。再给出一个字符串 tt 。我们可以将 ss 重复任意多次,直到满足 ttss 的子序列为止,问最少需要让 ss 重复多少次?

例如: ssabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzttaaaaaa ,那么最少需要让 ss 重复 33 次,才满足 ttss 的子序列。

输入格式

第一行:包含 2626 个小写字母 ' aa' 到 ' zz' 的字符串 ss 。 第二行:一个只包含小写字母的字符串 tttt 的长度小于等于 10001000

输出格式

输出 ss 需要重复的最小次数。

数据范围

对于 10%10\% 的数据, t5|t| \le 5

对于 50%50\% 的数据,保证字母表顺序与通常的英文字母表相同。

对于 100%100\% 的数据, t1000|t| \le 1000

输入样例 1

abcdefghijklmnopqrstuvwxyz
mood

输出样例 1

3