Pagini recente » Cod sursa (job #823842) | Cod sursa (job #832480) | Cod sursa (job #1250552) | Cod sursa (job #735135) | Cod sursa (job #102810)
Cod sursa(job #102810)
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define maxn 600003
#include <set>
#include <vector>
#include <bitset>
using namespace std;
char T[10000001];
int n;
//bool used[10000001];
vector<long long>H[maxn+2];
long long A[50001];
int N,CNT;
inline int insrt(char x[])
{
int n=0;
while(x[n]>='a' && x[n]<='c') ++n;
long long t=0;
for(int i=0;i<n;++i)
t=4*t+x[i]-'a'+1;
//if(A[N]!=t) A[++N]=t;
int h=(int)(t%maxn);
H[h].push_back(t);
}
void read()
{
int i, j;
freopen("abc2.in","r",stdin);
gets(T);
n=0;
while(T[n]>='a' && T[n]<='c') ++n;
int nr=0;
while(!feof(stdin))
{
char x[32];
gets(x);
insrt(x);
}
for(i=0;i<maxn;++i) sort(H[i].begin(), H[i].end());
for(i=0;i<maxn;++i)
if(H[i].size())
{
int tt[1000], nt=1;
tt[1]=H[i][0];
for(j=1;j<H[i].size();++j)
if(H[i][j]==H[i][j-1]);
else tt[++nt]=H[i][j];
H[i].clear();
for(j=1;j<=nt;++j) H[i].push_back(tt[j]);
}
//sort(A+1, A+N+1);
//for(CNT=1; CNT<=N; CNT<<=1);
}
/*
inline int find(long long v)
{
int h=(int)(v%maxn);
for(nod *p=H[h]; p ; p=p->n)
if(p->v==v)return 1;
return 0;
}
*/
inline int fnd(long long v)
{
int i, cnt;
for(i=1, cnt=(CNT); cnt ; cnt>>=1)
if(i+cnt<=N)
if(A[i+cnt]<=v) i+=cnt;
if(A[i]==v)return 1;
return 0;
}
int main()
{
read();
freopen("abc2.out","w",stdout);
int i, j;
long long p;
int nr=0, ok,h;
vector<long long>::iterator it;
for(i=0;i<n;++i)
//if(!used[i])
{
p=0;
for(j=i;j<i+20;++j)
{
p=p*4+T[j]-'a'+1;
// printf("%lld\n", p);
ok=0;
h=(int)(p%maxn);
//for(it=H[h].begin();it!=H[h].end();++it)
//if(*it==p) { ok=1; break;}
if(binary_search(H[h].begin(), H[h].end(), p))
{
++nr;
// used[i]=1;
break;
}
}
}
printf("%d\n", nr);
return 0;
}