CCC '20 S3 Easy - Searching for Strings
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
Write a program to count the number of substring of \(H\) which are considered as permutations of \(N\).
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 consists of one integer, the number of substrings of \(H\) which are permutations of \(N\).
Output for Sample Input
Explanation of Output for Sample Input
baa each appear as substrings of \(H\) (the former appears twice), while the permutation
aab does not appear.