Pagini recente » Profil robertpoe | Diferente pentru utilizator/dornescuvlad intre reviziile 102 si 81 | Monitorul de evaluare | Diferente pentru utilizator/dornescuvlad intre reviziile 102 si 59 | Cod sursa (job #1984579)
#include<cstdio>
#include<cstring>
#include<cmath>
const int nmax=2000005;
const int mod=666013;
const int mod2=326323;
const int baza=103;
char a[nmax],b[nmax];
int st[1005],top=0;
inline int getnum(char c)
{
return c-'A';
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int putere=1,theone=0,n,i,j,check=0,cnt=0,n1,n2,check2=0,theone2=0,putere2=1;
gets(a+1);
gets(b+1);
n1=strlen(a+1);
n2=strlen(b+1);
if(n1>n2)
{
printf("0");
return 0;
}
for(i=1;i<=n1;i++)
{
check=((check*baza)+getnum(b[i]))%mod;
check2=((check2*baza)+getnum(b[i]))%mod2;
theone=((theone*baza)+getnum(a[i]))%mod;
theone2=((theone2*baza)+getnum(a[i]))%mod2;
putere=putere*baza%mod;
putere2=putere2*baza%mod2;
}
if(check==theone)
{
cnt++;
st[++top]=0;
}
for(i=2;i<=n2-n1+1;i++)
{
check=(check*baza-getnum(b[i-1])*putere+getnum(b[i+n1-1]))%mod;
check2=(check2*baza-getnum(b[i-1])*putere2+getnum(b[i+n1-1]))%mod2;
if(check==theone&&check2==theone2)
{
cnt++;
if(cnt<=1000)
st[++top]=i-1;
}
}
printf("%d\n",cnt);
for(i=1;i<=top;i++)
printf("%d ",st[i]);
}