Canadian Computing Competition: 2020 Stage 1, Senior #3
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.
For ~3~ of the ~15~ available marks, ~|N| \le 8~ and ~|H| \le 200~.
For an additional ~2~ of the ~15~ available marks, ~|N| \le 200~ and ~|H| \le 200~.
For an additional ~2~ of the ~15~ available marks, ~|N| \le 2\,000~ and ~|H| \le 2\,000~.
Because the original test data were weak, an additional subtask worth ~5~ marks has been added.
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.