Pagini recente » Cod sursa (job #737093) | Cod sursa (job #2188267) | Cod sursa (job #2626085) | Cod sursa (job #1508917) | Cod sursa (job #2106417)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char sir[10000010];
char cuv[22];
int m;
const int mod=7013;
unsigned put[22];
vector<unsigned int>H[mod];
vector<unsigned int>::iterator it;
unsigned int hashh(char v[])
{
unsigned rez=0;
for(int i=0;i<m;i++)
{
rez=((rez*3)+v[i]-'a');
}
return rez;
}
void baga(unsigned int x)
{
H[x%mod].push_back(x);
}
bool cauta(unsigned int x)
{
int zum=x%mod;
for(it=H[zum].begin();it!=H[zum].end();it++)
{
if(*it==x) return 1;
}
return 0;
}
int main()
{
fin>>sir;
fin>>cuv;
int n=strlen(sir),i,nr=0;
m=strlen(cuv);
put[0]=1;
for(i=1;i<=20;i++)
{
put[i]=put[i-1]*3;
}
baga(hashh(cuv));
while(fin>>cuv)
{
baga(hashh(cuv));
}
unsigned int rez=hashh(sir);
if(cauta(rez)) nr++;
for(i=m;i<n;i++)
{
rez=(rez-((sir[i-m]-'a')*put[m-1]));
rez=((rez*3)+sir[i]-'a');
if(cauta(rez)==1) nr++;
}
fout<<nr;
}