Pagini recente » Cod sursa (job #877934) | Cod sursa (job #1315104) | Cod sursa (job #685794) | Cod sursa (job #1678569) | Cod sursa (job #470735)
Cod sursa(job #470735)
#include<fstream>
#include<vector>
#include<math.h>
#define dmax 10000004
#define dmax2 50004
#define md 666013
#define bz 3
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char l[dmax],cuv[23];
unsigned int m;
unsigned int sol;
vector<unsigned int>g[md+100];
vector<unsigned int>::iterator it;
void geth()
{ unsigned int nr=0,n,i,k;
n=strlen(cuv);
for(i=0;i<n;i++)
nr=nr*3+cuv[i]-'a';
k=nr%md;
for(it=g[k].begin();it<g[k].end();it++)
if(*it==nr)
return;
g[k].push_back(nr);
}
void search()
{ unsigned int i,lng,h=0,k;
for(i=0;i<m;i++)
h=bz*h + l[i]-'a' ;
k=h%md;
if(!g[k].empty() )
for(it=g[k].begin();it<g[k].end();it++)
if(*it==h)
sol++;
lng=strlen(l);
for(i=0;i < lng-m ;i++)
{
h=bz*(h-(l[i]-'a')*(int)pow(bz,m-1))+l[i+m]-'a';
k=h%md;
if(!g[k].empty() )
for(it=g[k].begin();it<g[k].end();it++)
if(*it==h)
sol++;
}
}
int main()
{ int i;
in.getline(l,dmax,'\n');
while(!in.eof() )
{ in.getline(cuv,23,'\n');
geth();
}
in.close();
m=strlen(cuv);
search();
out<<sol;
out.close();
return 0;
}