CCC '20 S3 Easy - Searching for Strings

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Note: This problem is modified from a problem which originated from the 2020 CCC Senior contest. CBOJ is in no way affiliated with the CEMC.

You're given a string \(N\), called the needle, and a string \(H\), called the haystack, both of which contain only lowercase letters a..z.

Write a program to count the number of substring of \(H\) which are considered as permutations of \(N\).

Input Specification

The first line contains \(N\) \((1 \le |N| \le 200\,000)\), the needle string.

The second line contains \(H\) \((1 \le |H| \le 200\,000)\), the haystack string.

Output Specification

Output consists of one integer, the number of substrings of \(H\) which are permutations of \(N\).

Sample Input


Output for Sample Input


Explanation of Output for Sample Input

The permutations aba and baa each appear as substrings of \(H\) (the former appears twice), while the permutation aab does not appear.


There are no comments at the moment.