# | Problem | Pass Rate (passed user / total user) |
---|---|---|
12532 | Simple Pattern Matching of Substrings |
|
13398 | Two-Phase Sorting 2 |
|
Description
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”
- all substrings with length 3 = {“aba”, “bab”, “aba”}
- frequency of S' = 2
Hint:
To efficiently check if a substring S' and P have the same pattern as required by this problem:
- use two 1D arrays to record the numbers of each kind of letters in S' and P, respectively;
- Just like the example above. TP[0] = the number of ‘a’ in P, TP[1] = the number of ‘b’ in P, and so on
- check if each pair of corresponding elements in the two 1D arrays are equal.
Input
One string S and an integer N on the first line.
Another string P on the second line.
- 1 ≤ N ≤ 3,000
- 1 ≤ |S|, |P| ≤ 3,000
- S, P contain only lower-case English letters.
Output
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.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Denny just learned the sorting method in school.
Sorting once is too easy for him, so the teacher asked a question that needs to be sorted twice to test him.
In this question, you will get a string V, and N strings of length 6, you need to sort the strings internally according to the order of the string V, and then sort the N strings in dictionary order. All strings contain only lower-case letters.
For example:
N = 2
S1 = abcabc, S2 = ababab
V = cbadefghijklmnopqrstuvwxyz
Internally sorted string: S1 = ccbbaa, S2 = bbbaaa
The sorted string after sorting: bbbaaa ccbbaa
Input
The first line contains a integer N, the number of strings you need to sort
The second line contains a string V
The following line contains N strings S1 ~ SN
testcase:
(3/6) 1 <= N <= 100, V = abcdefghijklmnopqrstuvwxyz
(3/6) 1 <= N <= 100, V = the permutation of a~z
Output
The Output contains only one line, the sorted string after sorting.
note: remember to add a '\n' in the end of output