Pagini recente » Cod sursa (job #1510044) | Cod sursa (job #1333966) | Cod sursa (job #1269085) | Cod sursa (job #1275046) | Cod sursa (job #114311)
Cod sursa(job #114311)
#include <stdio.h>
#include <algorithm>
#define MOD 92457
#define pow(x) (1u<<(x))
#define f(x) ((x>>12)^(x%(1u<<20)))
#define set(x) mask[f(x)/32] |= pow(f(x) & 31)
#define ok(x) (mask[f(x)/32] & pow(f(x) & 31))
using namespace std;
struct rec {
int p, val;
};
char text[10<<20];
unsigned n, lung, L;
unsigned aloc = MOD, mask[1<<17];
rec h[MOD+(50100)];
inline void baga(int x)
{
unsigned key = x;
set(x);
key %= MOD;
while (h[key].p){
if (h[key].val == x) return;
key=h[key].p;
}
h[key].p = aloc++;
h[key].val = x;
}
inline int exista(int x)
{
unsigned key = x;
if (!ok(x)) return 0;
key %= MOD;
while (h[key].p){
if (h[key].val==x) return 1;
key=h[key].p;
}
return 0;
}
inline unsigned lungime(char *s){
unsigned k=0, x=0;
while ('a'<=s[k] && s[k]<='c')
x = 3*x + (s[k++]-'a');
baga(x);
return k;
}
int main()
{
unsigned i;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(text, 10<<22, stdin);
char lin[30];
fgets(lin, 30, stdin);
lung = lungime(lin);
while (lungime(lin)==lung){
if (fgets(lin, 30, stdin)==NULL){
n++;
break;
}
}
n--;
unsigned nr, sol, pow=1;
for (i=1; i<lung; i++)
pow*=3;
for (i=nr=0; i<lung; i++)
nr=nr*3+(text[i]-'a');
while ('a'<=text[L] && text[L]<='c') L++;
for (i=lung, sol=exista(nr); i<L; i++){
nr-=(text[i-lung]-'a')*pow;
nr=3*nr+(text[i]-'a');
sol += exista(nr);
}
printf("%d\n", sol);
}