Pagini recente » Cod sursa (job #1433631) | Cod sursa (job #2713529) | Cod sursa (job #48140) | Cod sursa (job #1170681) | Cod sursa (job #496536)
Cod sursa(job #496536)
#include <stdio.h>
#include <string.h>
struct hash
{
long nod,val;
hash *link;
}*H[1000000];
char a[2000002],b[2000002];
long n,m,B,M,i,sir,aux,pow,nr,v[1002];
void add(long x,long pos)
{
hash *p;
p=new hash;
p->nod=x;
p->val=pos;
p->link=H[x%M];
H[x%M]=p;
}
long ver(long x)
{
long i;
for(i=x;i<=x+n;i++)
if(a[i-x]!=b[i]) return 0;
return 1;
}
long src(long x,long ok)
{
hash *p,*q;
p=H[x%M];
while(p!=NULL)
{
if(p->nod==x)
{
if(ok==0) return p->val;
else
if(ver(p->val))
{
if(p->link!=NULL) q->link=p->link;
else q->link=NULL;
return p->val;
}
}
if(ok==1) q=p;
p=p->link;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,2000002,stdin);
fgets(b,2000002,stdout);
n=strlen(a);
if(a[n]=='\n') n--;
m=strlen(b);
if(b[n]=='\n') m--;
M=999983;
B=0;
for(i=0;i<=n;i++)
{
aux=src(a[i],0);
if(aux==0)
{
add(a[i],++B);
a[i]=B;
}
else a[i]=aux;
}
for(i=0;i<=m;i++)
{
aux=src(b[i],0);
if(aux==0)
{
add(b[i],++B);
b[i]=B;
}
else b[i]=aux;
}
for(i=1;i<=M;i++) H[i]=NULL;
pow=1;
sir=0;
for(i=0;i<=n;i++)
{
sir+=pow*b[i];
sir%=M;
pow*=B;
pow%=M;
}
add(sir,0);
for(i=n+1;i<=m;i++)
{
sir*=B;
sir+=b[i]-pow*b[i-n-1];
sir%=M;
add(sir,i-n);
}
pow=1;
sir=0;
for(i=0;i<=n;i++)
{
sir+=pow*a[i];
sir%=M;
pow*=B;
pow%=M;
}
aux=src(sir,1);
nr=0;
while(aux!=0)
{
v[++nr]=aux;
if(nr>1000) break;
aux=src(sir,1);
}
printf("%ld\n",nr);
for(i=1;i<=nr;i++)
printf("%ld ",v[i]);
printf("\n");
return 0;
}