시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB58522818045.000%

문제

당신은 문자열 $S$를 선물 받았다. 하지만 당신은 오직 문자열 $T$만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, $T$ 역시 모든 문자가 서로 다르다.

그러던 당신에게 좋은 생각이 떠올랐다. 바로 $S$의 문자들을 골라내서 $T$를 만드는 것이다! 당신은 $S$에서 문자들을 골라내서 $S$에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 $S$의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, $S$가 "aabb"이면 첫 번째 문자 "a"와 세 번째 문자 "b"를 골라 문자열 "ab"를 만들고, 다시 두 번째 문자 "a"와 네 번째 문자 "b"를 골라 문자열 "ab"를 만들 수 있다.

당신은 $T$를 가능한 한 많이 만들고 싶다. 만들 수 있는 $T$의 최대 개수를 구하는 프로그램을 작성해보자.

입력

첫째 줄과 둘째 줄에 영어 알파벳 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. ($1\leq \left|S \right|\leq 10^6$, $1\leq \left|T \right|\leq 26$, $\left|T \right|\leq \left|S \right|$, $\left|S \right|$와 $\left|T \right|$는 각각 $S$의 길이와 $T$의 길이를 의미한다.)

$T$의 모든 문자는 서로 다르다.

출력

첫째 줄에 만들 수 있는 문자열 $T$의 최대 개수를 출력한다.

예제 입력 1

aabb
ab

예제 출력 1

2

예제 입력 2

aabb
ba

예제 출력 2

0

예제 입력 3

abba
ab

예제 출력 3

1