Pagini recente » Profil M@2Te4i | Monitorul de evaluare | Statistici catalina andreea (cata_smiles) | Cod sursa (job #2008446) | Cod sursa (job #100448)
Cod sursa(job #100448)
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define maxx 10000010
#define maxn 50010
#define maxl 25
#define mod 666013
#define pb push_back
#define us unsigned int
int n,m,L,sol;
char a[maxx],u[maxx];
char b[maxn][maxl];
int p[maxn],l[maxn];
vector <us> hash[mod];
int cmp(int x,int y)
{
return l[x]<l[y];
}
inline int search(us x)
{
int y=x%mod,i,l=hash[y].size();
for (i=0;i<l;i++)
if (x==hash[y][i]) return 1;
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
scanf("%s ",a+1);
a[0]=' ';
n=strlen(a)-1;
int i,j;
us x,y;
while (!feof(stdin))
{
m++;
scanf("%s ",b[m]+1);
b[m][0]=' ';
l[m]=strlen(b[m])-1;
p[m]=m;
}
sort(p+1,p+m+1,cmp);
for (i=1;i<=m && n>=l[p[i]];)
{
for (j=0;j<mod;j++) vector <us> ().swap(hash[j]);
for (L=l[p[i]];i<=m && L==l[p[i]];i++)
{
x=0;
for (j=1;j<=L;j++) x=x*3+(b[p[i]][j]-'a');
hash[x%mod].pb(x);
}
x=0,y=1;
for (j=1;j<=L;j++)
{
x=x*3+(a[j]-'a');
if (j>1) y*=3;
}
for (j=L+1;j<=n+1;j++)
{
if (!u[j-L] && search(x))
{
sol++;
u[j-L]=1;
}
x=x-y*(a[j-L]-'a');
x*=3;
if (j<=n) x+=a[j]-'a';
}
}
printf("%d\n",sol);
return 0;
}