문제
진흥나라에서는 공주가 좋아하는 문자열을 아름다운 문자열이라 명명하였다. 아름다운 문자열은 영문대문자로 구성되어 있다.
이웃나라와 게임을 하여 영문대문자로 구성된 긴 문자열을 획득하였다.
여기에서 아름다운 문자열과 같은 개수의 연속된 문자열을 발췌하여 아름다운 문자열을 만들려고 한다.
발췌한 문자열의 순서는 마음대로 바꿀 수 있으므로 아름다운 문자열과 각 문자의 개수만 같으면 아름다운 문자열을 만들 수 있다.
진흥나라의 공주는 아름다운 문자열을 만들기 위해 발췌할 수 있는 방법이 몇 가지나 있는지 궁금하였다.
진흥나라 공주를 위해 아름다운 문자열을 만들 수 있는 방법의 수를 구하는 프로그램을 작성해 주자.
입력
입력의 첫 번째 줄에는 아름다운 문자열 S가 입력된다.
두 번째 줄에는 게임으로 획득한 문자열 W가 입력된다.
S의 길이는 3이상 3,000 이하이고 W의 길이는 S의 길이 이상 100,000 이하이다.
모든 문자열은 영문 대문자로 구성되어 있다.
출력
W의 연속된 문자를 발췌하여 S를 만들 수 있는 경우의 수를 출력한다.
예제
ABC
BABCABBCA
4
힌트
출처
2018 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.