CCC '20 S3 - Searching for Strings
Note: This problem 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 distinct permutations of \(N\) which appear as a substring of \(H\) at least once. Note that \(N\) can have anywhere between \(1\) and \(|N|!\) distinct permutations in total – for example, the string
aab has \(3\) distinct permutations (
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 distinct permutations of \(N\) which appear as a substring of \(H\).
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.