Cod sursa(job #530941)
#include <fstream>
#include <cstring>
#include <list>
using namespace std;
const char InFile[]="abc2.in";
const char OutFile[]="abc2.out";
const int MaxN=10111000;
const int MaxL=21;
const int MOD=666017;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_el
{
int cod;
int count;
};
char str[MaxN],cuv[MaxL];
int N,L,sol,cpow,cod;
list<s_el> H[MOD];
inline void add(int key)
{
int hash=key%MOD;
list<s_el>::iterator it;
for(it=H[hash].begin();it!=H[hash].end();++it)
{
if(it->cod==key)
{
break;
}
}
if(it!=H[hash].end())
{
++it->count;
}
else
{
s_el el;
el.cod=key;
el.count=1;
H[hash].push_back(el);
}
}
inline int get(int key)
{
int hash=key%MOD;
list<s_el>::iterator it;
for(it=H[hash].begin();it!=H[hash].end();++it)
{
if(it->cod==key)
{
break;
}
}
if(it!=H[hash].end())
{
int t=it->count;
it->count=0;
return t;
}
return 0;
}
int main()
{
fin>>str;
fin>>cuv;
N=strlen(str);
L=strlen(cuv);
cod=0;
for(register int i=0;i<L;++i)
{
str[i]-='a';
cod*=3;
cod+=str[i];
}
cpow=1;
for(register int i=1;i<L;++i)
{
cpow*=3;
}
add(cod);
for(register int i=L;i<N;++i)
{
str[i]-='a';
cod-=cpow*str[i-L];
cod*=3;
cod+=str[i];
add(cod);
}
while(!fin.eof())
{
cod=0;
for(register int i=0;i<L;++i)
{
cod*=3;
cod+=cuv[i]-'a';
}
sol+=get(cod);
fin>>cuv;
}
fin.close();
fout<<sol;
fout.close();
return 0;
}