题目内容

给定 [a−z]，2626 个英文字母小写字符串组成的字符串 A 和 B，其中 A 可能存在重复字母，B 不会存在重复字母，现从字符串 A 中按规则挑选一些字母，可以组成字符串 B 。

挑选规则如下：

同一个位置的字母只能挑选一次 被挑选字母的相对先后顺序不能被改变 求最多可以同时从 A 中挑选多少组能组成 B 的字符串。

输入描述

输入为 2 行，第 1 行输入字符串 A ，第 2 行输入字符串 B，行首行尾没有多余空格，其中：

A、B 均由 [a−z] 26 个英文小写字母组成

0<A.length<100，A 中可能包含重复字母

0<B.length<10，B 中不会出现重复字母

输出描述

输出 1 行，包含 1 个数字，表示最多可以同时从 A 中挑选多少组能组成 B 的字符串

行末没有多余空格

备注

无需验证输入格式和输入数据合法性

样例1

输入

badc
bac

输出

1

说明

从字符串 A（"badc"）中可以按字母相对先后顺序取出字符串 B（"bac"）

样例2

输入

badc
abc

输出

0

说明

从字符串 A（"badc"）中无法按字母相对先后顺序取出字符串 B（"bac"）

样例3

输入

aabbcxd
abcd

输出

1

说明

从字符串 A（"aabbcxd"）中挑选一组 B（"abcd"）后，A中剩余字符串为 "abx"，无法再挑选出 "abcd"

样例4

输入

ababcecfdc
abc

输出

2

说明

从按如下步骤（步骤不唯一），可以同时从字符串 A（"ababcecfdc"）中最多取出两个 B（"abc"），其中颜色标注的是每步提取的字母：

剩余的 "efdc" 无法继续提取 "abc"，结果为 2

样例5

输入

aaa
a

输出

3

说明

从字符串 A（"aaa"）中可以挑选出 3 个字符串 B（"a"）