Pagini recente » ausoara | K-Lexicografic | Profil valentino | Diferente pentru implica-te/scrie-articole intre reviziile 122 si 70 | Cod sursa (job #96768)
Cod sursa(job #96768)
Utilizator |
Airinei Adrian astronomy |
Data |
3 noiembrie 2007 12:47:47 |
Problema |
Abc2 |
Scor |
Ascuns |
Compilator |
c |
Status |
done |
Runda |
|
Marime |
1.45 kb |
#include <stdio.h>
#include <string.h>
#define MOD (1<<28)-1
#define base 3
char T[1<<25], sir[10000100];
int res, L, N, put;
int ok(int val)
{
if( T[val>>3] & (1<<(val&7)) ) return 1;
return 0;
}
void baga(int val)
{
T[val>>3] |= (1<<(val&7));
}
void read_and_solve(void)
{
int i, j, k, v1, v2, val;
char aux[32];
fgets(sir, 1<<24, stdin);
N = strlen(sir);
if(sir[N-1] == '\n') N--;
while( !feof(stdin) )
{
scanf("%s\n", &aux);
if(!L) L = strlen(aux);
for(v1 = v2 = 0, i = 0; i < L; i++)
v1 = (v1*base+(aux[i]-'a')) & ((1<<24)-1),
v2 = (v2*base+(aux[i]-'a')) & ((1<<23)-1);
val = (v2*67+v1) & MOD;
baga(val);
}
for(put = 1, i = 1; i <= L; i++)
put = (put*base) & MOD;
for(val = 0, i = 0; i < N; i++)
{
v1 = (v1*base+(sir[i]-'a')) & ((1<<24)-1),
v2 = (v2*base+(sir[i]-'a')) & ((1<<23)-1);
if(i >= L)
v1 = (v1-(put*(sir[i-L]-'a'))&((1<<24)-1)+(1<<24))&((1<<24)-1),
v2 = (v2-(put*(sir[i-L]-'a'))&((1<<23)-1)+(1<<23))&((1<<23)-1);
val = (v2*67+v1) & MOD;
if(i >= L-1 && ok(val))
res++;
}
printf("%d\n", res);
}
int main(void)
{
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
read_and_solve();
return 0;
}