Pagini recente » Cod sursa (job #758166) | Cod sursa (job #954758) | Cod sursa (job #166690) | Cod sursa (job #329414) | Cod sursa (job #118617)
Cod sursa(job #118617)
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001
struct nod { char s[21]; long ord; int p; } P[Nmax];
char T[Lmax];
long i, j, N, n, m, q=27, d=3, h, t, rez;
void sort(long pp, long qq)
{
long st=pp, dr=qq;
nod X=P[st];
while (st<dr)
{
while (st<dr && P[dr].p>=X.p) dr--; P[st]=P[dr];
while (st<dr && P[st].p<=X.p) st++; P[dr]=P[st];
}
P[st]=X;
if (st-1>pp) sort(pp,st-1);
if (st+1<qq) sort(st+1,qq);
}
long search(long pp, long qq)
{
long m=(pp+qq)/2;
if (P[m].p==t) { for ( ; P[m-1].p==t; m--); return m; }
else if (m==pp || m==qq) return -1;
else if (P[m].p<t) return search(m,qq);
else return search(pp,m);
}
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[(P[++N].ord=N)].s);
fclose(stdin);
m=strlen(P[1].s);
for (h=i=1; i<m; i++) h=(h*d)%q;
for (i=1; i<=N; i++) for (j=0; j<m; j++) P[i].p=(d*P[i].p+P[i].s[j]-'a'+1)%q;
sort(1,N);
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 (j=search(1,N); j>0 && P[j].p==t; j++)
if (egal(P[j].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("%ld", rez);
fclose(stdout);
return 0;
}