문서 검색

영어 소문자와 공백으로만 이루어진 문서에서 어떤 단어가 몇 번 등장하는지 세려고 한다. 단, 한 글자라도 겹치는 두 등장은 동시에 셀 수 없다.

예를 들어 문서가 abababa이고 찾으려는 단어가 ababa라면, 단어는 0번째 위치에서도 시작할 수 있고 2번째 위치에서도 시작할 수 있다. 하지만 두 등장은 서로 겹치므로 둘 다 셀 수는 없다.

문서와 찾으려는 단어가 주어졌을 때, 서로 겹치지 않게 선택할 수 있는 단어의 등장 횟수의 최댓값을 구하시오.

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다.

둘째 줄에 찾고 싶은 단어가 주어진다. 단어의 길이는 최대 50이다.

문서와 단어는 알파벳 소문자와 공백으로만 이루어져 있다.

단어가 문서에 서로 겹치지 않게 등장할 수 있는 최대 횟수를 첫째 줄에 출력한다.