시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.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 "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 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.

서브태스크

번호배점제한
110

$K = 1$

215

$K \le 2$

330

$K \le 3$

420

$K \le 4$

510

$K \le 5$

625

$K \le 20$

예제 입력 1

18 4 1
ababbabaabaaabaaaa
aa
ab
ba
bb

예제 출력 1

4
5
5
1

예제 입력 2

20 6 2
bcababbabaabaaabaaaa
aaab
aabb
abbb
abba
cabc
caba

예제 출력 2

8
5
5
6
1
6

예제 입력 3

20 4 3
bcababbabaabaaabaaaa
abbbba
baaaab
abbacc
abbcca

예제 출력 3

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".

출처

Contest > Swedish Coding Cup > Swedish Coding Cup Finals 2021 C번

  • 문제를 만든 사람: Simon Lindholm

채점 및 기타 정보

  • 예제는 채점하지 않는다.