Pagini recente » Cod sursa (job #703902) | Cod sursa (job #1147667) | Cod sursa (job #647981) | Cod sursa (job #2877283) | Cod sursa (job #2295920)
#include <fstream>
#include <vector>
#include <string>
#include<math.h>
#define M 393241
#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=pow(3,lcuvant-1);
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;
}