Problem S3: Searching for Strings

Problem DescriptionCopy Anchor Link

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 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 (“aab", “aba", and “baa").

Input SpecificationCopy Anchor Link

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 2000$ and $|H| \le 2000$.

Output SpecificationCopy Anchor Link

Output consists of one integer, the number of distinct permutations of $N$ which appear as a substring of $H$.

Sample InputCopy Anchor Link

aab
abacabaa

Output for Sample InputCopy Anchor Link

2

Explanation of Output for Sample InputCopy Anchor Link

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