Pagini recente » Cod sursa (job #2354192) | Cod sursa (job #2101465) | Cod sursa (job #1633368) | Cod sursa (job #1665285) | Cod sursa (job #1516549)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2000001];
int cate;
long long x=1,y=1,n1=100021,n2=100007,i,j,k,l,n,r1,r2,q,nr1,nr2,v[1001],nrr1=0,nrr2=0;
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)%n1+q)%n1;
nr2=((nr2*123)%n2+q)%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++)
{
int x1,y1;
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)%n1;
nrr2=(nrr2*123+q)%n2;
if(nrr1==nr1&&nrr2==nr2)
{
cate++;
if(cate<=1000)
v[cate]=i;
}
}
printf("%d\n",cate);
int q1q=min(cate,1000);
for(i=1;i<=q1q;i++)
printf("%lld ",v[i]);
}
return 0;
}