Pagini recente » Cod sursa (job #2801761) | Cod sursa (job #1581275) | Cod sursa (job #121720) | Cod sursa (job #2634881) | Cod sursa (job #683409)
Cod sursa(job #683409)
#include<cstdio>
#include<vector>
#include<cstring>
#define infile "abc2.in"
#define outfile "abc2.out"
#define t_max 10000005
#define n_max 50005
#define Base 3
#define dim_max 21
#define MOD 90907
#define ui unsigned int
#define FOR(g) \
for(vector<ui>::iterator it=g.begin(); it!=g.end(); ++it)
using namespace std;
char T[t_max], S[dim_max];
int N, M, NrCuv;
vector < ui > HT[MOD];
ui Val[n_max];
ui Sol;
inline int tonum ( char x ){
return x - 'a'; }
void make_hash()
{
if(!strlen(S))
return;
if(!M)
M = strlen(S);
ui x = 0;
for(int i=0; i < M; ++i)
x = Base * x + tonum(S[i]);
int where = x % MOD;
FOR(HT[where])
if(*it == x)
return;
Val[++NrCuv] = x;
HT[where].push_back(x);
}
void citeste()
{
freopen(infile, "r", stdin);
gets(T);
N = strlen(T);
while(gets(S))
make_hash();
fclose(stdin);
}
void Rabin_Karp()
{
ui ValT = 0, P = 1;
for(int i=0; i < M; ++i)
{
ValT = Base * ValT + tonum(T[i]);
if(i)
P = Base * P;
}
for(int i=0; i <= N - M; ++i)
{
for(int j=1; j <= NrCuv; ++j)
if(Val[j] == ValT)
Sol++;
ValT = Base * (ValT - tonum(T[i]) * P) + tonum(T[i+M]);
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", Sol);
fclose(stdout);
}
int main()
{
citeste();
Rabin_Karp();
afiseaza();
return 0;
}