a865. Searching for Strings - Zero1 Online Judge System

Content

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

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

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

Sample Input #1

aab
abacabaa

Sample Output #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (3%): 1.0s , <1K
公開測資點#1 (3%): 0.07874015748031496s , <1K
公開測資點#2 (3%): 0.07874015748031496s , <1K
公開測資點#3 (3%): 0.07874015748031496s , <1K
公開測資點#4 (3%): 0.07874015748031496s , <1K
公開測資點#5 (3%): 0.07874015748031496s , <1K
公開測資點#6 (3%): 0.07874015748031496s , <1K
公開測資點#7 (3%): 0.07874015748031496s , <1K
公開測資點#8 (3%): 0.07874015748031496s , <1K
公開測資點#9 (3%): 0.07874015748031496s , <1K
公開測資點#10 (3%): 0.07874015748031496s , <1K
公開測資點#11 (3%): 0.07874015748031496s , <1K
公開測資點#12 (3%): 0.07874015748031496s , <1K
公開測資點#13 (3%): 0.07874015748031496s , <1K
公開測資點#14 (3%): 0.07874015748031496s , <1K
公開測資點#15 (3%): 0.07874015748031496s , <1K
公開測資點#16 (3%): 0.07874015748031496s , <1K
公開測資點#17 (3%): 0.07874015748031496s , <1K
公開測資點#18 (3%): 0.07874015748031496s , <1K
公開測資點#19 (3%): 0.07874015748031496s , <1K
公開測資點#20 (3%): 0.07874015748031496s , <1K
公開測資點#21 (3%): 0.07874015748031496s , <1K
公開測資點#22 (3%): 0.07874015748031496s , <1K
公開測資點#23 (3%): 0.07874015748031496s , <1K
公開測資點#24 (4%): 0.07874015748031496s , <1K
公開測資點#25 (4%): 0.07874015748031496s , <1K
公開測資點#26 (4%): 0.07874015748031496s , <1K
公開測資點#27 (4%): 0.07874015748031496s , <1K
公開測資點#28 (4%): 0.07874015748031496s , <1K
公開測資點#29 (4%): 0.07874015748031496s , <1K
公開測資點#30 (4%): 0.07874015748031496s , <1K

Hint ：

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

Tags:

出處:

[管理者：

cplei@g.puic... (李振邦Lei Chan Pon...)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」