시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 596 | 127 | 71 | 17.706% |
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.
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.
Olympiad > Canadian Computing Competition & Olympiad > 2020 > CCC 2020 Senior Division 3번