CCC '20 S3 - Searching for Strings

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.5s
Memory limit: 512M

Author:
Problem types
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 az.

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 Specification

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 Specification

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

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 H (the former appears twice), while the permutation aab does not appear.


Comments

There are no comments at the moment.