문자 해독

마야 문자를 해독하는 일은 예상보다 훨씬 어렵다. 아직도 뜻이 완전히 밝혀진 문자는 많지 않으며, 본격적인 해독 연구가 진전되기 시작한 지도 오래되지 않았다.

마야 문자는 소리를 나타내는 여러 그림 문자로 이루어져 있다. 이런 문자들은 다양한 위치에서 결합되어 하나의 단어를 만든다.

해독을 어렵게 하는 중요한 이유 중 하나는 단어를 읽는 순서이다. 고대의 기록자는 단어를 일정한 규칙에 따라 쓰기보다 보기 좋게 보이도록 문자들을 배치했다. 그래서 연구자가 어떤 단어를 이루는 각 그림 문자의 발음을 알아내더라도, 그 단어를 실제로 어떤 순서로 발음했는지는 확정하기 어렵다.

연구자들은 특정 단어 W가 벽화 문자열 S 안에 숨어 있는지 찾고 있다. W를 이루는 g개의 그림 문자는 이미 알고 있지만, 이 문자들이 S 안에서 어떤 순서로 나타나는지는 알 수 없다.

단어 W와 벽화에서 추출한 문자열 S가 주어졌을 때, S의 길이 g인 부분 문자열 중 W의 문자들을 재배열한 것과 같은 경우가 몇 개인지 구하시오.

첫째 줄에 찾으려는 단어 W의 길이 g와 벽화 문자열 S의 길이 |S|가 공백으로 구분되어 주어진다. (1 <= g <= 3000, g <= |S| <= 3,000,000)

둘째 줄에는 W가, 셋째 줄에는 S가 주어진다. 두 문자열은 모두 알파벳 대문자와 소문자로 이루어지며, 대소문자를 서로 다른 문자로 구분한다.

S 안에서 W의 순열이 될 수 있는 길이 g의 부분 문자열 개수를 출력한다.