Pagini recente » Cod sursa (job #2204342) | Cod sursa (job #2278258) | Cod sursa (job #1313807) | Cod sursa (job #2372534) | Cod sursa (job #1003821)
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define pb push_back
#define maxn 10000005
#define maxm 25
#define MOD 666013
using namespace std;
typedef unsigned int ui;
int n,m,sol;
char t[maxn],s[maxm];
vector <ui> l[MOD];
int hash_key(ui k){
return k%MOD;
}
void insert(ui val)
{
int k=hash_key(val);
l[k].pb(val);
}
int search(ui val)
{
int k=hash_key(val);
for(unsigned int i=0;i<l[k].size();i++)
if(l[k][i]==val) return 1;
return 0;
}
void read()
{
ui nr,f;
scanf("%s\n",t+1);
n=strlen(t+1);
while(!feof(stdin))
{
scanf("%s\n",s+1);
m=strlen(s+1); nr=0; f=1;
for(int i=m;i;i--)
nr+=(s[i]-'a')*f,f*=3;
insert(nr);
}
}
void solve()
{
ui nr=0,f=1;
if(m>n) {sol=0; return;}
for(int i=m;i;i--)
nr+=(t[i]-'a')*f,f*=3;
if(search(nr)) sol++;
f/=3;
for(int i=m+1;i<=n;i++)
{
nr-=(t[i-m]-'a')*f;
nr*=3; nr+=t[i]-'a';
if(search(nr)) sol++;
}
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
read();
solve();
printf("%d",sol);
fclose(stdin);
fclose(stdout);
return 0;
}