IOI '06 - Merida, Yucatan, Mexico
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 . 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
glyphs from
and a
sequence
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
.
Write a program that, given the glyphs for and the sequence
of
glyphs in the carvings, counts the number of possible appearances of
in
; that is, every sequence of consecutive
glyphs in
that is
a permutation of the glyphs in
.
Input Specification
The first line of input contains two space-separated integers: , the
number of glyphs in
and
, the number of
glyphs in the sequence
.
The second line contains consecutive characters that represent the
glyphs in
. Valid characters are the uppercase and lowercase
characters of the Roman alphabet. Uppercase and lowercase characters are
considered to be different.
The third line contains consecutive characters that represent the
glyphs in the carvings. Valid characters are the uppercase and lowercase
characters of the Roman alphabet. Uppercase and lowercase characters are
considered to be different.
Output Specification
One integer on a single line, the number of possible appearances of
in
.
Grading
In some test cases worth of the total marks,
will be
no more than
.
Sample Input
4 11
cAda
AbrAcadAbRa
Sample Output
2
Comments