Canadian Computing Competition: 2020 Stage 1, Senior #3
You're given a string , called the needle, and a string
, called the haystack, both of which contain only lowercase letters
a
…z
.
Write a program to count the number of distinct permutations of which appear as a substring of
at least once. Note that
can have anywhere between
and
distinct permutations in total – for example, the string
aab
has distinct permutations (
aab
, aba
, and baa
).
Input Specification
The first line contains
, the needle string.
The second line contains
, the haystack string.
For of the
available marks,
and
.
For an additional of the
available marks,
and
.
For an additional of the
available marks,
and
.
Because the original test data were weak, an additional subtask worth marks has been added.
Output Specification
Output consists of one integer, the number of distinct permutations of which appear as a substring of
.
Sample Input
aab
abacabaa
Output for Sample Input
2
Explanation of Output for Sample Input
The permutations aba
and baa
each appear as substrings of (the former appears twice), while the permutation
aab
does not appear.
Comments