시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 23 4 4 44.444%

문제

두 문자열 S와 T가 주어진다. T는 알파벳 소문자로만 이루어져 있고, S는 알파벳 소문자와 물음표로만 이루어져 있다.

S의 모든 물음표를 알파벳 소문자로 바꾸려고 한다. 이때, S의 부분 문자열로 등장하는 T의 개수를 최대로 만들어보자.

입력

첫째 줄에 S, 둘째 줄에 T가 주어진다. S와 T의 길이는 100,000보다 작거나 같고, 두 길이를 곱한 값은 10,000,000보다 작거나 같다.

출력

S의 물음표를 알파벳 소문자로 바꿨을 때, 부분 문자열로 등장할 수 있는 T의 개수의 최댓값을 출력한다.

예제 입력 1

winlose???winl???w??
win

예제 출력 1

5

winlosewinwinlwinwin

예제 입력 2

glo?yto?e??an?
or

예제 출력 2

3

glorytoreorand

예제 입력 3

??c?????
abcab

예제 출력 3

2

abcabcab

출처