Pagini recente » Cod sursa (job #284310) | Cod sursa (job #561295) | Cod sursa (job #1202394) | Cod sursa (job #484418) | Cod sursa (job #166735)
Cod sursa(job #166735)
#include <vector>
#include <stdio.h>
#include <string>
#include <algorithm>
#define mx 10000010
#define bz 9999999
using namespace std;
struct nod
{
char el[24];
nod *ua;
} *l[bz+1];
char s[mx+4];
char str[24];
long long v[4];
long i,j,n,nm,h,nr;
long long x;
void clad(long t)
{
nod *p;
p=new nod;
strcpy(p->el+1,str+1);
p->ua=l[t];
l[t]=p;
}
int comp(long x, char s[])
{
long i;
nod *p;
p=l[x];
int ok=0;
while (p)
{
for (i=1; i<=h; i++)
if ((p->el)[i]!=str[i])
break;
if (i==h+1)
{
ok=1;
break;
}
p=p->ua;
}
return ok;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(s+1,mx+4,stdin);
nm=strlen(s+1)-1;
while (!feof(stdin))
{
fgets(str+1,25,stdin);
h=strlen(str+1)-1;
x=0;
for (i=1; i<=h; i++)
x=(x*3+str[i]-96)%bz;
if (comp(x,str)==0)
clad(x);
}
v[1]=1;
for (i=1; i<=h; i++)
v[1]=v[1]*3%bz;
v[2]=v[1]*2%bz;
v[3]=v[1]*3%bz;
v[1]=v[1]%bz;
x=0;
for (i=1; i<=h; i++)
{
x=(x*3+s[i]-96)%bz;
str[i]=s[i];
}
if (comp(x,str))
nr++;
for (i=h+1; i<=nm; i++)
{
strcpy(str+1,str+2);
str[h]=s[i];
x=(x*3+s[i]-96)%bz;
x=(x-v[s[i-h]-96]);
if (x<0)
x=x+bz;
if (comp(x,str))
nr++;
}
printf("%ld",nr);
fclose(stdin);
fclose(stdout);
return 0;
}