Pagini recente » Cod sursa (job #2705581) | Cod sursa (job #1091273) | Cod sursa (job #1042108) | Istoria paginii runda/eusebiu_oji_2012_10/clasament | Cod sursa (job #1477236)
#include <cstdio>
#include <cstring>
#define MOD1 1013
#define MOD2 97
#define MOD3 53
#define DIM 27
#define DIM_TXT 10000007
using namespace std;
int h1, h2, h3, put1[DIM], put2[DIM], put3[DIM], ct, n, sze;
char s[DIM], txt[DIM_TXT], loc[MOD1+2][MOD2+2][MOD3+2];
void init()
{
put1[0] = 1;
for(int i = 1; i< DIM; ++i) put1[i] = (3*put1[i-1])%MOD1;
put2[0] = 1;
for(int i = 1; i< DIM; ++i) put2[i] = (3*put2[i-1])%MOD2;
put3[0] = 1;
for(int i = 1; i< DIM; ++i) put3[i] = (3*put3[i-1])%MOD3;
}
void citire()
{
scanf("%s", txt+1);
n = strlen(txt+1);
while(scanf("%s", s+1) == 1)
{
if(!sze) sze = strlen(s+1);
h1 = 0;
h2 = 0;
h3 = 0;
for(int i = 1; i<= sze; ++i)
{
h1 = (h1 + put1[sze-i] * (s[i] - 'a'))%MOD1;
h2 = (h2 + put2[sze-i] * (s[i] - 'a'))%MOD2;
h3 = (h3 + put3[sze-i] * (s[i] - 'a'))%MOD3;
}
loc[h1][h2][h3] = 1;
//printf("%s\n", s+1);
//printf("h1 = %d h2 = %d h3 = %d\n", h1, h2, h3);
}
}
void solve()
{
h1 = 0;
h2 = 0;
h3 = 0;
for(int i = 1; i< sze; ++i)
{
h1 = (h1 + (txt[i]-'a')*put1[sze-i])%MOD1;
h2 = (h2 + (txt[i]-'a')*put2[sze-i])%MOD2;
h3 = (h3 + (txt[i]-'a')*put3[sze-i])%MOD3;
}
for(int i = sze; i<= n; ++i)
{
h1 = h1 + txt[i] - 'a'; if(h1 >= MOD1) h1 -= MOD1;
h2 = h2 + txt[i] - 'a'; if(h2 >= MOD2) h2 -= MOD2;
h3 = h3 + txt[i] - 'a'; if(h3 >= MOD3) h3 -= MOD3;
//printf("%s\n", txt +i-sze+1);
//printf("h1 = %d h2 = %d h3 = %d\n", h1, h2, h3);
if(loc[h1][h2][h3] == 1) ct++;
h1 = ((h1 - (txt[i-sze+1]-'a')*put1[sze-1] + MOD1)*3)%MOD1;
h2 = ((h2 - (txt[i-sze+1]-'a')*put2[sze-1] + MOD2)*3)%MOD2;
h3 = ((h3 - (txt[i-sze+1]-'a')*put3[sze-1] + MOD3)*3)%MOD3;
}
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
init();
citire();
solve();
printf("%d\n", ct);
return 0;
}