Pagini recente » Cod sursa (job #3038509) | Cod sursa (job #1127497) | Cod sursa (job #2710903) | Cod sursa (job #3038573) | Cod sursa (job #320270)
Cod sursa(job #320270)
#include<stdio.h>
#include<string.h>
#define nmax 2000010
#define p 70
#define mod1 1000000
#define mod2 1000070
char a[nmax],b[nmax],m[nmax];
int n1,n2,h1,h2,p1,p2;
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a,b);
n1=strlen(a);
n2=strlen(b);
p1=p2=1;
h1=h2=0;
for(int i=0;i<n1;i++){
h1=(h1*p+a[i])%mod1;
h2=(h2*p+a[i])%mod2;
if(i!=0){
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
if(n1>n2){
printf("0\n");
return 0;
}
int ha1=0,ha2=0;
for(int i=0;i<n1;i++)
{
ha1=(ha1*p+b[i])%mod1;
ha2=(ha2*p+b[i])%mod2;
}
int nr=0;
if(ha1==h1&&ha2==h2)
{
m[0]=1;
nr++;
}
for(int i=n1;i<n2;i++)
{
ha1=((ha1-(b[i-n1]*p1)%mod1+mod1)*p+b[i])%mod1;
ha2=((ha2-(b[i-n1]*p2)%mod2+mod2)*p+b[i])%mod2;
if(ha1==h1&&ha2==h2)
{
m[i-n1+1]=1;
nr++;
}
}
printf("%d\n",nr);
nr=0;
for(int i=0;i<n2&&nr<1000;i++)
if(m[i])
{
nr++;
printf("%d ",i);
}
printf("\n");
return 0;
}