Pagini recente » Cod sursa (job #2516328) | Cod sursa (job #3213557) | Monitorul de evaluare | Cod sursa (job #1027550) | Cod sursa (job #99156)
Cod sursa(job #99156)
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define INF "abc2.in"
#define OUF "abc2.out"
#define LMAX 10000002
#define HMAX 1046527
#define SG 1
#define GG 2
using namespace std;
char s[LMAX];
int n,m,sz;
inline int mctod(char c)
{
switch(c)
{
case 'a': return 1;
case 'b': return 2;
case 'c': return 3;
default :return 0;
}
}
inline long long hmap(char *v)
{
long long key=0;
while(*v)
{
key=key*4+mctod(*v);
++v;
}
return key;
}
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
int sol=0,p,i=0,j,st,dr,mij;
char word[32]={0};
long long k,delta;
vector <long long> q;
fgets(s,LMAX,in);
n=strlen(s);--n;
fgets(word,32,in);
m=strlen(word);--m;
// printf("%s %s",s,word);
k=hmap(word);
q.push_back(k);
while(fgets(word,32,in)){k=hmap(word);q.push_back(k);}//printf("%s",word);}
k=q[0];p=q.size();
for(i=1;i<p;++i) if(k>q[i]) k=q[i];
for(i=0;i<p;++i) q[i]-=k;//printf("%lld ",q[i]);}
delta=k;
sort(q.begin(),q.end());
//printf("\n");
i=0;
while(i+m<n)
{
for(j=0;j<m;++j) word[j]=s[i+j];
k=hmap(word);
k-=delta;
if(k>=0)
{
// printf("%lld ",k);
st=0;dr=p-1;
while(st<=dr)
{
mij=(st+dr)/2;
if(q[mij]==k) break;
if(q[mij]>k) dr=mij-1;
else st=mij+1;
}
if(k==q[mij]) ++sol;
}
++i;
}
/* long long alfa=0;
for(i=1;i<23;++i)
{
alfa=alfa*4+3;
printf("%lld\n",alfa);
}*/
fprintf(out,"%d",sol);
fclose(in);fclose(out);
return 0;
}