Pagini recente » Cod sursa (job #545776) | Cod sursa (job #1112457) | Cod sursa (job #1220986) | Cod sursa (job #427886) | Cod sursa (job #306256)
Cod sursa(job #306256)
#include<cstdio>
#include<string>
using namespace std;
#define MAX_L 10000004
#define MAX_C 24
#define Mod 666013
#define B 3
char s[MAX_L];
int n;
int L, N;
int nr;
struct Tabela
{
int nr;
Tabela *urm;
};
Tabela *H[Mod];
void insert(int x)
{
Tabela *q;
int h = x % Mod;
for(q=H[h];q;q=q->urm) if(q->nr == x) return;
Tabela *p = new Tabela;
p->urm = H[h]; p->nr = x;
H[h] = p;
}
int find(int x)
{
Tabela *q;
int h = x%Mod;
for(q=H[h];q;q=q->urm) if(q->nr == x) return 1;
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
scanf("%s\n",s+1);
char cuv[MAX_C]; int i;
int hash, P, pr = 1;
s[0] = '!';
L = strlen(s) - 1;
while(!feof(stdin))
{
memset(cuv,0,sizeof(cuv));
scanf("%s\n",cuv+1);
cuv[0] = '!';
N = strlen(cuv) - 1;
hash = 0; P = 1;
for(i=1;i<=N;++i)
{
hash = hash + P*(cuv[i] - 'a');
P = P*B;
}
insert(hash);
}
P = 1; hash = 0;
for(i=L-N+1;i<=L;++i)
{
hash += P*(s[i]-'a');
P*=B;
}
pr = P / B;
i = L-N;
nr += find(hash);
for(i = L-N;i>0;--i)
{
hash -= pr * (s[i+N] - 'a');
hash *= B;
hash += (s[i] - 'a');
nr += find(hash);
}
printf("%d\n",nr);
return 0;
}