|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||1024 MB||0||0||0||0.000%|
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 "ﬀ", 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 havi
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.
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.
$K = 1$
$K \le 2$
$K \le 3$
$K \le 4$
$K \le 5$
$K \le 20$
18 4 1 ababbabaabaaabaaaa aa ab ba bb
4 5 5 1
20 6 2 bcababbabaabaaabaaaa aaab aabb abbb abba cabc caba
8 5 5 6 1 6
20 4 3 bcababbabaabaaabaaaa abbbba baaaab abbacc abbcca
6 9 6 6
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".