Pagini recente » Cod sursa (job #55713) | Cod sursa (job #2625106) | Cod sursa (job #1702639) | Cod sursa (job #1525651) | Cod sursa (job #1659579)
#include <cstdio>
#include <string.h>
using namespace std;
char x[2000005],y[2000005];
int q,w,putere1,putere2,h1,h2,v1,v2,i,b1,b2,mod1,mod2,total;
struct nod
{
int x;
nod *next;
}*p,*ult;
void adauga(int x)
{
nod *crt;
if(p==NULL)
{
p=new nod;
p->x=x;
p->next=NULL;
ult=p;
}
else
{
crt=new nod;
crt->x=x;
crt->next=NULL;
ult->next=crt;
ult=crt;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",x,y);
w=strlen(x);
q=strlen(y);
if(w>q)
{
printf("0");
return 0;
}
p=new nod;
p=NULL;
ult=p;
b1=73;
b2=b1;
mod1=100021;
mod2=100007;
putere1=1;
putere2=1;
for(i=0;i<w;i++)
{
h1=(h1*b1+x[i])%mod1;
h2=(h2*b2+x[i])%mod2;
v1=(v1*b1+y[i])%mod1;
v2=(v2*b2+y[i])%mod2;
if(i!=0)
{
putere1=(b1*putere1)%mod1;
putere2=(b2*putere2)%mod2;
}
}
if(h1==v1&&h2==v2)
{
total++;
adauga(0);
}
for(;y[i]!=0;i++)
{
v1=((v1-(y[i-w]*putere1)%mod1+mod1)%mod1*b1+y[i])%mod1;
v2=((v2-(y[i-w]*putere2)%mod2+mod2)%mod2*b2+y[i])%mod2;
if(h1==v1&&h2==v2)
{
total++;
adauga(i-w+1);
}
}
printf("%d\n",total);
int contor=0;
for(nod *crt=p;crt!=NULL&&contor<1000;crt=crt->next)
{
printf("%d ",crt->x);
contor++;
}
return 0;
}