|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||18||5||4||40.000%|
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.
Output consists of one integer, the number of distinct permutations of N which appear as a substring of H.
The permutations “aba” and “baa” each appear as substrings of H (the former appears twice), while the permutation “aab” does not appear.