Pagini recente » Cod sursa (job #1685407) | Cod sursa (job #3198933) | Cod sursa (job #979583) | Cod sursa (job #968139) | Cod sursa (job #2385525)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
unsigned int nr,ok,i,sol,n,m;
unsigned int p1=127,p2=13;
char s[10000005];
char s2[55];
unsigned int z2,z1,k,pp1,pp2,x1[50005],y1,x2[50005],y2;
FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");
struct nod{
int inf;
nod *urm;
}*l[10008];
void adaug(nod *&p,int x){
nod *u=new nod;
u->inf=x;
u->urm=p;
p=u;
}
int verif(unsigned int val){
unsigned int poz=val%10007;
for(nod * j=l[poz];j;j=j->urm)
if(j->inf==val) return 1;
return 0;
}
int cautbin(unsigned int n,unsigned int val,unsigned int ad[]){
int mij;
int p=1;
int u=n;
while(p<=u){
mij=(p+u)/2;
if(ad[mij]==val) return mij;
else if(val<ad[mij]) u=mij-1;
else p=mij+1;
}
return -1;
}
int main()
{
fgets(s,10000005,f);pp1=pp2=1;
while(!feof(f)){
fscanf(f,"%s",s2);
nr++;
k=strlen(s2);
z1=z2=0;
for(i=0; i<k; i++)
{
//x1[nr]=x1[nr]*p1+s2[i];
//x2[nr]=x2[nr]*p2+s2[i];
z1=z1*p1+s2[i];
z2=z2*p2+s2[i];
if(i!=0&&!ok){ pp1*=p1;
pp2*=p2;}
}
if(!verif(z1)) adaug(l[z1%10007],z1);
ok=1;
}
for(i=0; i<=k-1; i++)
{
y1=y1*p1+s[i];
y2=y2*p2+s[i];
}
//sort(x1+1,x1+nr+1);
//sort(x2+1,x2+nr+1);
int nrsol=0,a1,a2;
if(verif(y1)) nrsol++;
// a1=cautbin(nr,y1,x1);
// a2=cautbin(nr,y2,x2);
// if(a1!=-1&&a2!=-1) nrsol++;
int n=strlen(s);
for(i=k; i<n; i++)
{
y1=p1*(y1-s[i-k]*pp1)+s[i];
y2=p2*(y2-s[i-k]*pp2)+s[i];
if(verif(y1)) nrsol++;
// a1=cautbin(nr,y1,x1);
// a2=cautbin(nr,y2,x2);
// if(a1!=-1&&a2!=-1)nrsol++;
}
fprintf(g,"%d\n",nrsol);
return 0;
}