Pagini recente » Cod sursa (job #2072326) | Cod sursa (job #1898537) | Cod sursa (job #2613446) | Cod sursa (job #322419) | Cod sursa (job #1514748)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2000001];
int cate;
long long x=123,y=123,n1=100021,n2=100007,i,j,k,l,n,r1,r2,q,nr1,nr2,v[1001],nrr1=0,nrr2=0;
void taiere()
{
long long qq=n-2;
while(qq!=0)
{
if(qq%2==0)
{
x=x*x;
y=y*y;
qq/=2;
}
else
{
qq--;
x*=123;
y*=123;
}
y=y%n2; x=x%n1;
}
}
int main ()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s);
n=strlen(s);
for(i=0;i<n;i++)
{
q=s[i];
nr1=nr1*123+q;
nr2=nr2*123+q;
nr1%=n1;
nr2%=n2;
if(i!=0){
x=(x*123)%n1;
y=(y*123)%n2;
}
}
gets(s);
int h=strlen(s);
//taiere();
if(h<n)
printf("0\n");
else
{
nrr1=0,nrr2=0;
for(i=0;i<n;i++)
{
q=s[i];
nrr1=nrr1*123+q;
nrr2=nrr2*123+q;
nrr1%=n1;
nrr2%=n2;
}
if(nrr1==nr1&&nrr2==nr2)
{
cate++;
v[cate]=0;
}
for(i=1;i<=h-n;i++)
{
long long x1,y1;
if(i==474)
i=474;
x1=(x*s[i-1])%n1;
y1=(y*s[i-1])%n2;
nrr1-=x1;
nrr2-=y1;
if(nrr1<0)
nrr1+=n1;
if(nrr2<0)
nrr2+=n2;
q=s[i+n-1];
nrr1=nrr1*123+q;
nrr2=nrr2*123+q;
nrr1%=n1;
nrr2%=n2;
if(nrr1==nr1&&nrr2==nr2)
{
cate++;
if(cate<=1000)
v[cate]=i;
}
}
printf("%lld\n",cate);
int q1q=min(cate,1000);
for(i=1;i<=q1q;i++)
printf("%lld ",v[i]);
}
return 0;
}