Problem H
Ligatures
Vivi works as a font designer. She is almost done with her new masterpiece but thinks that something is missing. She has therefore decided to add some ligatures. A ligature occurs when two characters are combined into a single glyph. For example, “ff” often becomes “ff”, and “ae” would sometimes become “æ” in old Latin writing.
Vivi knows the importance of choosing the right ligature – with luck, maybe her ligature will become as lasting as the ligature “&” (which comes from the Latin word “et”, meaning “and”)! Typically, ligatures are selected for character pairs that occur often. A good set of ligatures will not include too many unique ligatures but will result in many occurrences.
Taking this task very seriously, Vivi has come up with $Q$ suggestions for possible ligature sets, with $K$ ligatures in each. She now asks you to test each of her suggestions against her corpus, and determine the number of ligature occurrences for each suggested set.
It is important to note that the corpus is read from left to right, and ligatures can’t be combined. Thus, with ligatures for “ab”, “bc“, and “cd“, the string “abcd” would count as having just two ligature occurrences – the one for “bc“ would never get used.
Input
The first line of the input contains three integers: $N$ – the size of the corpus ($1 \le N \le 10^6$); $Q$ – the number of suggestions ($1 \le Q \le 10^5$); and $K$ – the number of ligatures in each suggested set ($1 \le K \le 20$).
The second line of the input contains a string with $N$ characters from a-z: the corpus.
The next $Q$ lines each contain $2K$ characters: the ligature suggestions. The first two characters make up the first suggested ligature, the second two characters make up the second one, and so on. No character pair will occur twice within a suggestion.
Output
For each suggested ligature set, output a line with the number of ligature occurrences within the corpus, if the corpus is read from left to right and the given ligatures are applied.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
1 |
10 |
$K = 1$ |
|
2 |
15 |
$K \le 2$ |
|
3 |
30 |
$K \le 3$ |
|
4 |
20 |
$K \le 4$ |
|
5 |
10 |
$K \le 5$ |
|
6 |
25 |
$K \le 20$ |
Explanation of Samples
The three samples correspond to the first three subtasks.
In the first query of the first sample, the ligature “aa” occurs as “ababbab aa ba aa b aa aa”. It occurs 4 times.
In the first query of the second sample, we have the ligatures “aa” and “ab”. Reading the corpus from left to right, we get the 8 occurrences: “bc ab ab b ab aa b aa ab aa aa”.
| Sample Input 1 | Sample Output 1 |
|---|---|
18 4 1 ababbabaabaaabaaaa aa ab ba bb |
4 5 5 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
20 6 2 bcababbabaabaaabaaaa aaab aabb abbb abba cabc caba |
8 5 5 6 1 6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 4 3 bcababbabaabaaabaaaa abbbba baaaab abbacc abbcca |
6 9 6 6 |
