Pagini recente » Cod sursa (job #293327) | Cod sursa (job #1130367) | Cod sursa (job #2059800) | Cod sursa (job #235643) | Cod sursa (job #2295928)
#include <fstream>
#include <vector>
#include <string>
#include<math.h>
#define M 10041
#define N 10000050
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector <unsigned int> hashtable[M];
int verify(unsigned int value)
{
unsigned int indice=value%M;
for(unsigned int i=0; i < hashtable[indice].size(); i++)
{
if(hashtable[indice][i] == value)
{
return 1;
}
}
return 0;
}
unsigned int lsir,lcuvant;
unsigned int i ,j, sol,value,rollinghash;
string cuvant,sir;
int main()
{
fin>>sir;
fin>>cuvant;
lcuvant=cuvant.size();
value=0;
for(i=0;i<=lcuvant-1;i++)
{
value = value*3+cuvant[i]-'a';
}
hashtable[value%M].push_back(value);
while(fin>>cuvant)
{
value=0;
for(i=0;i<=lcuvant-1;i++)
{
value=value*3+cuvant[i]-'a';
}
if(verify(value)==0)
{
hashtable[value%M].push_back(value);
}
}
unsigned int power=1;
for(i=1;i<=lcuvant-1;i++)
{
power=power*3;
}
rollinghash=0;
for(i=0;i<=lcuvant-1;i++)
{
rollinghash=rollinghash*3+sir[i]-'a';
}
sol=0;
sol=sol+verify(rollinghash);
lsir=sir.size();
for(i=lcuvant;i<=lsir-1;i++)
{
rollinghash=rollinghash-power*(sir[i - lcuvant]-'a');
rollinghash=rollinghash*3+(sir[i]-'a');
sol=sol+verify(rollinghash);
}
fout<<sol;
fin.close();
fout.close();
return 0;
}