題目描述

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”).

輸入格式

The first line contains N (1 <=|N|<= 200 000), the needle string.

The second line contains H (1 <= |H| <= 200 000), the haystack string.

For 3 of the 15 available marks, |N| <= 8 and |H| <= 200.

For an additional 2 of the 15 available marks, |N| <= 200 and |H| <= 200.

For an additional 2 of the 15 available marks, |N| <= 2000 and |H| <= 2000.

輸出格式

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

Samples

aab
abacabaa

2

提示

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

原始資料

• Zero1 題號：a865
• Hydro 題號：Z0865
• Locale：en_GB
• Display：open