Pagini recente » Istoria paginii utilizator/floryflor | Istoria paginii runda/simulare_oni | Istoria paginii runda/hgfdg | Rating Avasiloaei Ionut (ionut.avasiloaei) | Cod sursa (job #173344)
Cod sursa(job #173344)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define maxl 50010
#define ltext 1000010
#define prim 666013
char text[ltext];
char cuv[maxl][25];
int p[maxl],l[maxl],fol[maxl];
int nr[25];
int i,j,n,m,lung,nrcuv;
unsigned int k,put;
vector <unsigned int> hash[prim+10];
int comp(int x, int y)
{
return l[x]<l[y];
}
inline int apartine(unsigned int k)
{
int rest=k%prim,l=hash[rest].size(),i;
for (i=0; i<=l-1; i++)
if (hash[rest][i]==k) return 1;
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
scanf("%s",text+1);
text[0]=' ';
m=strlen(text)-1;
n=0;nrcuv=0;
while (!feof(stdin))
{
n++;
scanf("%s",cuv[n]+1);
cuv[n][0]=' ';
l[n]=strlen(cuv[n])-1;
p[n]=n;
nr[l[n]]++;
}
p[n]=0;n--;
sort(p+1,p+n+1,comp);
for (i=1; i<=n && l[p[i]]<=m;)
{
for (j=0; j<prim; j++)
vector <unsigned int> ().swap(hash[j]);
for (lung=l[p[i]]; i<=n && lung==l[p[i]]; i++)
{
k=0;
for (j=1; j<=l[p[i]]; j++)
k=k*3+cuv[p[i]][j]-'a';
hash[k%prim].push_back(k);
}
put=1;k=0;
for (j=1; j<=lung; j++)
{
k=k*3+text[j]-'a';
if (j>1) put*=3;
}
for (j=1; j<=m+1; j++)
fol[j]=0;
text[m+1]='a';
for (j=lung+1; j<=m+1; j++)
{
if (!fol[j-lung] && apartine(k))
{
nrcuv++;
fol[j-lung]=1;
}
k=k-put*(text[j-lung]-'a');
k=k*3+text[j]-'a';
}
}
printf("%d\n",nrcuv);
return 0;
}