Pagini recente » Cod sursa (job #2220098) | Arhiva de probleme | Cod sursa (job #1751617) | Cod sursa (job #1478204) | Cod sursa (job #118701)
Cod sursa(job #118701)
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001
#define q 93343517
#define d 3
struct nod { char s[21]; struct nod * urm; };
typedef nod * list;
char T[Lmax], P[21];
long long i, j, N, n, m, h, t, rez, p;
list H[q+1], pp;
int egal(char *A, char *B, long c)
{
for (int i=0; i<m; i++)
if (A[i]!=B[i+c]) return 0;
return 1;
}
int main()
{
freopen("abc2.in", "r", stdin);
scanf("%s\n", &T);
while (!feof(stdin))
{
scanf("%s\n", &P);
if (!m) m=strlen(P);
for (p=i=0; i<m; i++) p=(p*d+P[i]-'a'+1)%q;
if (!H[p])
{
H[p]=new nod;
H[p]->urm=NULL;
memcpy(H[p]->s,P,m);
}
else
{
list qq=new nod;
qq->urm=H[p];
memcpy(qq->s,P,m);
H[p]=qq;
}
}
fclose(stdin);
for (h=i=1; i<m; i++) h=(h*d)%q;
n=strlen(T);
for (i=0; i<m; i++) t=(d*t+T[i]-'a'+1)%q;
for (i=0; i<=n-m; i++)
{
for (pp=H[t]; pp; pp=pp->urm)
if (egal(pp->s,T,i))
{
rez++;
break;
}
t=(t+d*q-(T[i]-'a'+1)*h)%q;
t=(t*d+T[i+m]-'a'+1)%q;
}
freopen("abc2.out", "w", stdout);
printf("%lld", rez);
fclose(stdout);
return 0;
}