Description
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.
Input
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
Output the number of substrings in the book by correspondent Ovchinnikov, which are frightening for Martians.
Sample Input
| input | output |
|---|---|
aaa bbb ccc aaa aaa bbb ccc aaa zzz aaa bbb ccc |
3 |
Notes
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.
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=127; int cur[maxn*maxn*maxn]; int hash[maxn*maxn*maxn]; char s[4]; int change(char *s){ int res=0; for(int i=0;i<3;i++){ res=maxn*res+s[i]; } return res; } int h[550000]; int main(){ char c; int len=0; while(scanf("%s",s)!=EOF){ int temp=change(s); hash[temp]++; len++; c=getchar(); if(c==' ') break; } int ans=0; int cnt=0; for(int i=0;;i++){ scanf("%s",s); int d=change(s); h[i]=d; if(cur[d]<hash[d]) cnt++; cur[d]++; if(i>=len){ d=h[i-len]; if(cur[d]<=hash[d]) cnt--; cur[d]--; } if(cnt==len) ans++; c=getchar(); if(c==' ') break; } printf("%d ",ans); return 0; }