Pagini recente » Cod sursa (job #2119698) | Cod sursa (job #1909481) | Cod sursa (job #2828386) | Cod sursa (job #2176956) | Cod sursa (job #108324)
Cod sursa(job #108324)
#include<stdio.h>
#include<string.h>
#include<fstream.h>
#define NM 10000002
#define lmax 22
#define nmax 50002
#define nodmax 1000005
char ter[nodmax],sir[NM],c[nmax][lmax];
long f[nodmax][3],pref[nodmax],sol,N,l,n;
void read()
{long i;
freopen("abc2.in","r",stdin);
scanf("%s",&sir);
n=strlen(sir);
i=1;
while(!feof(stdin))
scanf("%s",&c[i++]);
N=i-2;
l=strlen(c[1]);
}
void make_trie()
{long val,nr,i,x,j,k,v[nodmax],vv[lmax],vvv[lmax],t[nodmax];
memset(t,0,sizeof(t));
memset(v,0,sizeof(v));
nr=0;
for(i=1;i<=N;i++)
{x=0;
for(j=0;j<l;j++)
{
val=c[i][j]-'a';
if(!f[x][val])
{
f[x][val]=++nr;
t[nr]=x;
v[nr]=val;
}
x=f[x][val];
}
ter[nr]=1;
}
for(i=1,x=0;i<=nr;i++)
if(t[i])
{
val=v[i];
x=pref[i-1];
while(!f[x][val]&&x)
x=pref[x];
x=f[x][val];
pref[i]=x;
}
}
void solve()
{long i,x,val;
x=0;
sol=0;
for(i=0;i<n;i++)
{
val=sir[i]-'a';
while(!f[x][val]&&x)
x=pref[x];
//if(!x&&f[0][val])
// x=f[0][val];
x=f[x][val];
if(ter[x])
sol++;
}
}
void print()
{
freopen("abc2.out","w",stdout);
printf("%ld",sol);
fclose(stdout);
}
int main()
{
read();
make_trie();
solve();
print();
return 0;
}