Pagini recente » Cod sursa (job #2973600) | Cod sursa (job #1259958) | Cod sursa (job #205399) | Cod sursa (job #2635849) | Cod sursa (job #96772)
Cod sursa(job #96772)
Utilizator |
Airinei Adrian astronomy |
Data |
3 noiembrie 2007 12:51:36 |
Problema |
Abc2 |
Scor |
Ascuns |
Compilator |
c |
Status |
done |
Runda |
|
Marime |
1.51 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, p1, p2, 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(p1 = p2 = 1, i = 1; i <= L; i++)
p1 = (p1*base) & ((1<<24)-1),
p2 = (p2*base) & ((1<<23)-1);
for(v1 = v2 = 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-(p1*(sir[i-L]-'a'))&((1<<24)-1)+(1<<24))&((1<<24)-1),
v2 = (v2-(p2*(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;
}