There are different superstitions on different planets. Martians laugh at
Earthlings suffering Triskaidekaphobia and Hexakosioihexekontahexaphobia.
And Earthlings make jokes on the fact that there is a scary word in
Martian language. Martians are not only afraid of the word itself, but
also of all the words that are obtained by rearrangement of letters in
The Martian alphabet has 729 000 letters. Correspondent Ovchinnikov, who
lives on Mars and studies Martian language, represents Martian letters as
triplets of symbols with ASCII codes from 33 to 122. He has recently
written a book about life and culture on Mars. Before sending the book
into press Ovchinnikov wants to count the number of substrings in the text
of the book which are frightening for Martians.
The first line contains the scary Martian word, consisting of at most 8 000
Martian letters. The second line contains the text of Ovchinnikov's book,
which is at most 500 000 Martian letters long. Both the
scary word and the text of the book contain at least one letter. Every
Martian letter is represented by the triplet of symbols with ASCII codes
from 33 to 122, each letter separated from the next one by a whitespace.
Output the number of substrings in the book by correspondent Ovchinnikov,
which are frightening for Martians.
aaa bbb ccc
aaa aaa bbb ccc aaa zzz aaa bbb ccc
Two substrings “aaa bbb ccc” (starting from the second and the seventh
positions in the text) and a substring “bbb ccc aaa” are scary for the
Problem Author: Andrey Demidov (prepared by Alex Samsonov)
Problem Source: Open Ural FU Personal Contest 2012