Writing

Official version
IOI’06

English

Version 1.3

Number of pages 1
IOI’06
Page 1
DECIPHERING THE MAYAN WRITING

Deciphering the Mayan writing has proven to be a harder task than anticipated by the early
investigations. After almost two hundred years, very little of it was actually understood. It has been
only in the last three decades that real advances have been made.

Mayan writing is based on small drawings known as glyphs which represent sounds. Mayan words
are normally written as glyphs put together at various positions.

One of several problems in deciphering Mayan writing arises in the order of reading. When placing
several glyphs in order to form a word, Mayan writers sometimes decided the position based more
on their own esthetic views than on any particular rule. This leads to the fact that, even though the
sound for many glyphs is known, sometimes archaeologists are not sure how to pronounce a
written word.

The archaeologists are looking for a special word W. They know the glyphs for it, but they don’t
know all the possible ways of arranging them. Since they knew you were coming to IOI’06, they
have asked for your help. They will provide you with the g glyphs from W and a sequence S of all
the glyphs (in the order they appear) in the carvings they are studying. Help them by counting the
number of possible appearances of the word W.

TASK
Write a program that, given the glyphs for W and the sequence S of glyphs in the carvings, counts
the number of possible appearances of W in S; that is, every sequence of consecutive g glyphs in S
that is a permutation of the glyphs in W.

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

1 ≤ g ≤ 3 000

the number of glyphs in W
g ≤ |S| ≤ 3 000 000
where |S| is the number of glyphs in the sequence S

Your program must read the following data from the file writing.in
writing.in
DESCRIPTION
4 11
cAda
AbrAcadAbRa
LINE 1: Contains 2 space-separated integers that represent g and |S|.
LINE 2: Contains g consecutive characters that represent the glyphs
in W. Valid characters are ‘a’-‘z’ and ‘A’-‘Z’; uppercase and
lowercase characters are considered different.
LINE 3: Contains |S| consecutive characters that represent the glyphs
in the carvings. Valid characters are ‘a’-‘z’ and ‘A’-‘Z’;
uppercase and lowercase characters are considered different.

Your program must write the following data to the file writing.out
writing.out
DESCRIPTION
2
LINE 1: Must contain the count of possible appearances of W in S.

GRADING
For a set of test cases worth a total of 50 points, each test run will meet the requirement that g ≤ 10.
IMPORTANT NOTE FOR PASCAL PROGRAMMERS
By default in FreePascal, a variable of type string has a size limit of 255 characters. If you want
to use strings longer than that, you should add the directive {$H+} to your code just below the
program ...; line.

생성자가 기록되지 않았습니다.

출처 IOI 2006