Pagini recente » Cod sursa (job #1459564) | Cod sursa (job #812961) | Cod sursa (job #1769872) | Cod sursa (job #1623916) | Cod sursa (job #114319)
Cod sursa(job #114319)
#include <cstdio>
#include <bitset>
#define MOD 152457
#define pow(x) (1u<<(x))
#define f(x) (x%(1u<<20))
#define set(x) mask[f(x)]=1;
#define ok(x) (mask[f(x)])
using namespace std;
struct rec {
int next, val;
};
char text[10<<20];
unsigned lung, L;
unsigned aloc = MOD;
bitset<(1<<20)> mask;
rec h[2*MOD];
inline void baga(int x)
{
unsigned key = x % MOD;
set(x);
while (h[key].next){
if (h[key].val == x) return;
key=h[key].next;
}
h[key].next = aloc++;
h[key].val = x;
}
inline int exista(int x)
{
// if (!ok(x)) return 0;
unsigned key = x%MOD;
while (h[key].next){
if (h[key].val==x) return 1;
key=h[key].next;
}
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) break;
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);
}