Pagini recente » Cod sursa (job #1255381) | Cod sursa (job #1654731) | Cod sursa (job #424321) | Cod sursa (job #2791663) | Cod sursa (job #2482758)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int mod1=100007, mod2=100021;
char sir[10000005], cuvant[25];
int hash1[50005], hash2[50005], ind, l, putere1=4, putere2=4, rez, hashcuv1, hashcuv2;
bool fr1[100010], fr[100010];
int create_hash(char *s, int l, int mod)
{
int sum=0;
int p=1;
for (int i=l-1; i>=0; --i)
{
sum=sum+(s[i]-'a'+1)*p;
p*=4;
p%=mod;
sum%=mod;
}
return sum;
}
void create_putere()
{
for (int i=2; i<l; ++i)
{
putere1*=4;
putere1%=mod1;
putere2*=4;
putere2%=mod2;
}
}
void solve()
{
hashcuv1=create_hash(sir, l, mod1);
hashcuv2=create_hash(sir, l, mod2);
for (int i=1; i<=ind; ++i)
{
if (hashcuv1==hash1[i] && hashcuv2==hash2[i])
rez++;
}
int lungime=strlen(sir);
int dif=lungime-l;
int auxhash1, auxhash2;
for (int i=1; i<=dif; ++i)
{
auxhash1=hashcuv1-(sir[i-1]-'a'+1)*putere1;
auxhash1%=mod1;
auxhash1*=4;
auxhash1+=(sir[i+l-1]-'a'+1);
auxhash1%=mod1;
auxhash2=hashcuv2-(sir[i-1]-'a'+1)*putere2;
auxhash2%=mod2;
auxhash2*=4;
auxhash2+=(sir[i+l-1]-'a'+1);
auxhash2%=mod2;
hashcuv1=auxhash1;
hashcuv2=auxhash2;
for (int j=1; j<=ind; ++j)
{
if (hashcuv1==hash1[j] && hashcuv2==hash2[j])
rez++;
}
}
g << rez;
}
int main()
{
int ah1, ah2;
f >> sir;
while (f>>cuvant)
{
if (ind==0)
l=strlen(cuvant);
ah1=create_hash(cuvant, l, mod1);
ah2=create_hash(cuvant, l, mod2);
if (fr[ah1]==0 || fr[ah2]==0)
{
hash1[++ind]=ah1;
hash2[ind]=ah2;
fr[ah1]=true;
fr[ah2]=true;
}
}
create_putere();
solve();
return 0;
}