Pagini recente » Cod sursa (job #2264332) | Cod sursa (job #206010) | Cod sursa (job #2248026) | Cod sursa (job #1276401) | Cod sursa (job #119352)
Cod sursa(job #119352)
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001
#define d 3
#define q 43517
struct nod {long loc; 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;
short uz[Lmax];
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);
n=strlen(T);
scanf("%s\n", &P); m=strlen(P);
freopen("abc2.in", "r", stdin); scanf("%s\n", &T);
for (h=i=1; i<m; i++) h=(h*d)%q;
for (i=0; i<m; i++) t=(t*d+T[i]-'a'+1)%q;
for (i=0; i<=n-m; i++)
{
if (!H[t])
{
H[t]=new nod;
H[t]->urm=NULL;
H[t]->loc=i;
}
else
{
list qq=new nod;
qq->urm=H[t];
qq->loc=i;
H[t]=qq;
}
t=(t+d*q-(T[i]-'a'+1)*h)%q;
t=(t*d+T[i+m]-'a'+1)%q;
}
while (!feof(stdin))
{
scanf("%s\n", &P);
for (p=i=0; i<m; i++) p=(p*d+P[i]-'a'+1)%q;
for (pp=H[p]; pp; pp=pp->urm)
if (!uz[pp->loc] && egal(P,T,pp->loc))
{
rez++;
uz[pp->loc]=1;
}
}
fclose(stdin);
freopen("abc2.out", "w", stdout);
printf("%lld", rez);
fclose(stdout);
return 0;
}