ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural FU Personal Contest 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Scary Martian Word

Time limit: 1.0 second
Memory limit: 64 MB
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 this word.
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 Martians.
Problem Author: Andrey Demidov (prepared by Alex Samsonov)
Problem Source: Open Ural FU Personal Contest 2012
To submit the solution for this problem go to the Problem set: 1941. Scary Martian Word