Pagini recente » Cod sursa (job #1589735) | Cod sursa (job #1490602) | Cod sursa (job #1247689) | Cod sursa (job #151011) | Cod sursa (job #107055)
Cod sursa(job #107055)
#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
#define sz(x) x.size()
using namespace std;
char s[LMAX];
int n,m,sz;
struct nod
{
unsigned k;
nod *next;
};
struct hnod
{
nod *p;
void pb(unsigned arg)
{
nod *op,*q;
op=new nod;
op->k=arg;op->next=NULL;
if(p==NULL) p=op;
else
{
if(arg<p->k)
{
op->next=p;
p=op;
}
else
{
q=p;
while(q->next&&arg>q->next->k) q=q->next;
if(arg!=q->k)
{
op->next=q->next;
q->next=op;
}
}
}
}
bool hset(unsigned arg)
{
nod *q;
q=p;
if(p==NULL) return false;
if(arg==p->k) return true;
else
{
while(q->next&&arg>=q->next->k) q=q->next;
if(q->k==arg) return true;
else return false;
}
}
void print()
{
nod *q;
q=p;
while(q){ printf("%d ",q->k);q=q->next;}
printf("\n");
}
}mh[HMAX];
inline unsigned mctod(char c)
{
switch(c)
{
case 'b': return 1;
case 'c': return 2;
default : return 0;
}
}
inline unsigned hmap(char *v)
{
unsigned key=0;
while(*v&&*v!='\n')
{
key=key*3+mctod(*v);
++v;
}
return key;
}
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
int sol=0,i,j;
char word[32]={0};
unsigned k,delta,tla[32];
fgets(s,LMAX,in);
n=strlen(s);--n;
tla[0]=1;
for(i=1;i<32;++i) tla[i]=tla[i-1]*3;//printf("%lld ",tla[i]);}
fgets(word,32,in);
m=strlen(word);--m;
k=hmap(word); // printf("%lld ",k);
mh[k%HMAX].pb(k);
while(fgets(word,32,in)) {k=hmap(word);mh[k%HMAX].pb(k);}// printf("%lld ",k);}
// printf("\n\n");
// mh[0].print();
// mh[1].print();
// mh[2].print();
i=0;
for(j=0;j<m;++j) word[j]=s[j];
k=hmap(word); //printf("%lld ",k);
if(mh[k%HMAX].hset(k)) ++sol;
i=1;
while(i+m-1<n)
{
delta=tla[m-1]*mctod(s[i-1]);
k=(k-delta)*3+mctod(s[i+m-1]);// printf("%lld ",k);
// delta=tla[m-1]*mctod(s[i]);
if(mh[k%HMAX].hset(k)) ++sol;
++i;
}
fprintf(out,"%d",sol);
fclose(in);fclose(out);
return 0;
}