Pagini recente » Cod sursa (job #487559) | Cod sursa (job #113107) | Cod sursa (job #1251095) | Cod sursa (job #721542) | Cod sursa (job #683097)
Cod sursa(job #683097)
#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 dim_max 21
#define Base 3
#define MOD1 100007
#define MOD2 100021
using namespace std;
char T[t_max];
int N;
char P[n_max][dim_max];
int NP;
bitset < MOD2 > uz1, uz2;
int Sol;
void citeste()
{
freopen(infile, "r", stdin);
gets(T);
N = strlen(T);
while(gets(P[++NP]));
fclose(stdin);
}
void Rabin_Karp(char *P)
{
int M = strlen(P);
int HP1, HP2, HT1, HT2;
int P1, P2;
HP1 = HP2 = HT1 = HT2 = 0;
P1 = P2 = 1;
for(int i=0; i<M; ++i)
{
HP1 = (Base * HP1 + P[i]) % MOD1;
HP2 = (Base * HP2 + P[i]) % MOD2;
HT1 = (Base * HT1 + T[i]) % MOD1;
HT2 = (Base * HT2 + T[i]) % MOD2;
if(i){
P1 = (Base * P1) % MOD1;
P2 = (Base * P2) % MOD2;
}
}
if(uz1[HP1] && uz2[HP2])
return;
uz1[HP1] = uz2[HP2] = 1;
for(int i=0; i<= N - M; ++i)
{
if(HT1 == HP1 && HT2 == HP2)
Sol++;
HT1 = (Base * (HT1 - (T[i] * P1) % MOD1 + MOD1) + T[i+M]) % MOD1;
HT2 = (Base * (HT2 - (T[i] * P2) % MOD2 + MOD2) + T[i+M]) % MOD2;
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", Sol);
fclose(stdout);
}
int main()
{
citeste();
for(int i=1; i < NP; ++i)
Rabin_Karp(P[i]);
afiseaza();
return 0;
}