Pagini recente » Cod sursa (job #1030681) | Rezultatele filtrării | Cod sursa (job #1069298) | Cod sursa (job #1364160) | Cod sursa (job #1984586)
#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)
{
if(c>='0'&&c<=9)
return c-'0'+1;
else if(c>='a'&&c<='z')
return c-'a'+11;
return c-'A'+37;
}
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=n1+1;i<=n2;i++)
{
check=(check*baza-(getnum(b[i-n1])*putere)%mod+getnum(b[i]))%mod;
check2=(check2*baza-(getnum(b[i-n1])*putere2)%mod2+getnum(b[i]))%mod2;
if(check==theone&&check2==theone2)
{
cnt++;
if(cnt<=1000)
st[++top]=i-n1;
}
}
printf("%d\n",cnt);
for(i=1;i<=top;i++)
printf("%d ",st[i]);
}