A substring S' of a given string S with length N is a contiguous sequence of N letters from S.
For instance, the substrings with length 2 of “abcde” are “ab”, “bc”, “cd”, “de”.
Given a string S and an integer N together with another string P.
Your task is to find all substrings from S with length N that have the same pattern as P, and the frequencies of these substrings.
In this problem, the patterns of two strings A, B are the same if and only if the numbers of each kind of letters in A, B are equal.
For example:
A = “ouo”, B = “oou” have the same pattern
| number of letter | a~n | o | p~t | u | v~z |
|---|---|---|---|---|---|
| A = “ouo” | 0 | 2 | 0 | 1 | 0 |
| B = “oou” | 0 | 2 | 0 | 1 | 0 |
A = “pap”, B = “oao” have different patterns
| number of letter | a | b~n | o | p | q~z |
|---|---|---|---|---|---|
| A = “pap” | 1 | 0 | 0 | 2 | 0 |
| B = “oao” | 1 | 0 | 2 | 0 | 0 |
Moreover, under a given N, the frequency of a substring S' is its number of occurrences within all resulting substrings of S.
For example: S = “ababa”, S' = “aba”
Hint:
To efficiently check if a substring S' and P have the same pattern as required by this problem:
One string S and an integer N on the first line.
Another string P on the second line.
Print on the first line the number M of distinct substrings of S with length N that have the same pattern as P.
On the following M lines, print the (S', F') pair for the M substrings that have the same pattern as P, where F' is the frequency of S', one pair per line, in decreasing order of their frequencies. When the frequencies tie, please use the lexicographical order of the substrings.
Remember ‘\n’ on the end of line.