Pagini recente » Cod sursa (job #1951537) | Cod sursa (job #1476922) | Cod sursa (job #2241972) | Cod sursa (job #2551990) | Cod sursa (job #496451)
Cod sursa(job #496451)
#include <stdio.h>
#include <string.h>
struct point
{
long nod;
point *link;
}*q;
struct hash
{
long nod;
long nr;
point *list;
hash *link;
}*H[1000000],*p;
long val,c,n,m,i,C,pos;
char a[2000002],b[2000002];
void add(long x,long pos,long i)
{
hash *p;
point *q;
long nr=0;
if(pos==0)
{
p=new hash;
p->nod=i;
p->nr=1;
q=new point;
q->nod=i;
q->link=p->list;
p->list=q;
p->link=H[x%C];
H[x%C]=p;
}
else
{
p=H[x%C];
for(nr=1;nr<=pos;nr++) p=p->link;
p->nr++;
q=new point;
q->nod=i;
q->link=p->list;
p->list=q;
}
}
long src(long x,long pos)
{
hash *p;
p=H[x%C];
long nr=0;
while(p!=NULL)
{
if(p->nod==pos) return nr;
nr++;
p=p->link;
}
return 0;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,2000002,stdin);
fgets(b,2000002,stdin);
val=0;
C=999983;
n=strlen(a)-1;
if(a[n]=='\n') n--;
m=strlen(b)-1;
if(b[m]=='\n') m--;
for(i=0;i<=n;i++)
val+=b[i];
add(val,0,0);
for(i=n+1;i<=m;i++)
{
val-=b[i-n];
val+=b[i];
pos=src(val,i);
add(val,pos,i-n);
}
val=0;
for(i=0;i<=n;i++)
val+=a[i];
p=H[val%C];
while(p!=NULL)
{
if(p->nod==val)
{
printf("%ld\n",p->nr);
q=p->list;
val=0;
while(q!=NULL&&val<=1000)
{
printf("%ld ",q->nod);
val++;
q=q->link;
}
printf("\n");
return 0;
}
p=p->link;
}
return 0;
}