Pagini recente » Cod sursa (job #2451433) | Cod sursa (job #90643) | Solutii preONI 2006, Runda a 4-a | Cod sursa (job #2317652) | Cod sursa (job #98444)
Cod sursa(job #98444)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define NMAX 10000010
#define Q 101869
struct nod
{
nod *next;
long long x;
};
void read();
void add(long long x);
char S[NMAX];
nod H[Q];
int M, N;
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
read();
return 0;
}
void read()
{
char A[32];
long long ok, la;
int i, j;
M = -1;
fgets(S, NMAX, stdin);
S[strlen(S) - 1] = 0;
for(i = 0; i < Q; i++)
H[i].x = -1;
for(;!feof(stdin);)
{
scanf("%s ", A);
if(M == -1) M = strlen(A);
ok = 0;
for(i = 0; i < M; i++)
ok = ok * 3 + A[i] - 'a';
add(ok);
}
N = strlen(S);
int rez = 0;
la = 1;
ok = 0;
if(M <= N)
for(i = 0; i < M; i++)
{
la = la * 3;
ok = ok * 3 + S[i] - 'a';
}
la /= 3;
nod *p;
for(i = 0; i + M <= N; i++)
{
for(p = H[ok % Q].next; p; p = p->next)
if(p->x == ok)
{
rez++;
break;
}
ok -= la * (S[i] - 'a');
ok *= 3;
if(i + M < N)
ok += S[i + M] - 'a';
}
printf("%d\n", rez);
}
void add(long long x)
{
nod *p, *r;
for(p = &H[x % Q]; p->next; p = p->next)
if(p->x == x)
return;
else if(p->x < x && (p->next->x) > x)
break;
r = new nod;
r->next = p->next;
p->next = r;
r->x = x;
}