Pagini recente » Cod sursa (job #750097) | Cod sursa (job #2307240) | Cod sursa (job #2470395) | Cod sursa (job #917894) | Cod sursa (job #683287)
Cod sursa(job #683287)
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#define infile "abc2.in"
#define outfile "abc2.out"
#define t_max 10000005
#define n_max 50005
#define Base 3
#define dim_max 21
#define MOD1 9931
#define MOD2 9923
using namespace std;
char T[t_max], S[dim_max];
unsigned int N, M;
unsigned int HP1[n_max], HP2[n_max];
unsigned int NH;
bitset < MOD1 > uz1, uz2;
unsigned int Sol;
inline int tonum ( char x ){
return x - 'a'; }
void make_hash()
{
if(!strlen(S))
return;
if(!M)
M = strlen(S);
HP1[++NH] = HP2[NH] = 0;
for(unsigned int i=0; i < M; ++i)
{
HP1[NH] = (Base * HP1[NH] + tonum(S[i])) % MOD1;
HP2[NH] = (Base * HP2[NH] + tonum(S[i])) % MOD2;
}
if(uz1[HP1[NH]] && uz2[HP2[NH]])
{ NH--; return;}
uz1[HP1[NH]] = uz2[HP2[NH]] = 1;
}
void citeste()
{
freopen(infile, "r", stdin);
gets(T);
N = strlen(T);
while(gets(S))
make_hash();
fclose(stdin);
}
void Rabin_Karp()
{
unsigned int HT1, HT2, P1, P2;
HT1 = HT2 = 0;
P1 = P2 = 1;
for(unsigned int i=0; i < M; ++i)
{
HT1 = (Base * HT1 + tonum(T[i])) % MOD1;
HT2 = (Base * HT2 + tonum(T[i])) % MOD2;
if(i)
{
P1 = (Base * P1) % MOD1;
P2 = (Base * P2) % MOD2;
}
}
for(unsigned int i=0; i <= N - M; ++i)
{
for(unsigned int j=1; j <= NH; ++j)
if(HP1[j] == HT1 && HP2[j] == HT2)
Sol++;
HT1 = (Base * (HT1 - (tonum(T[i]) * P1) % MOD1 + MOD1) + tonum(T[i+M])) % MOD1;
HT2 = (Base * (HT2 - (tonum(T[i]) * P2) % MOD2 + MOD2) + tonum(T[i+M])) % MOD2;
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", Sol);
fclose(stdout);
}
int main()
{
citeste();
Rabin_Karp();
afiseaza();
return 0;
}