Pagini recente » Cod sursa (job #225855) | Cod sursa (job #3256490) | Cod sursa (job #643770) | Cod sursa (job #1784870) | Cod sursa (job #1512241)
#include<cstdio>
#include<cstring>
char s[2000001];
int n1=666013,n2=1000000007,i,j,k,l,n,r1,r2,q,nr1,nr2,cate,v[1001],nrr1=0,nrr2=0;
void taiere(int i)
{
if(s[i]>='A'&&s[i]<='Z')
q=s[i]-'A';
if(s[i]>='a'&&s[i]<='z')
q=26+s[i]-'a';
if(s[i]>='0'&&s[i]<='9')
q=52+s[i]-'0';
int x=62,y=62,qq=n-2;
while(qq!=0)
{
if(qq%2==0)
{
x=x*x;
y=y*y;
qq/=2;
}
else
{
qq--;
x*=62;
y*=62;
}
x=x%n1;
y=y%n2;
}
x*=q;
y*=q;
x%=n1;
y%=n2;
nrr1-=x;
nrr2-=y;
if(nrr1<0)
nrr1+=n1;
if(nrr2<0)
nrr2+=n2;
}
int main ()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s);
n=strlen(s);
for(i=0;i<n;i++)
{
if(s[i]>='A'&&s[i]<='Z')
q=s[i]-'A';
if(s[i]>='a'&&s[i]<='z')
q=26+s[i]-'a';
if(s[i]>='0'&&s[i]<='9')
q=52+s[i]-'0';
nr1=nr1*62+q;
nr2=nr2*62+q;
nr1%=n1;
nr2%=n2;
}
gets(s);
int h=strlen(s);
if(h<n)
printf("0");
else
{
nrr1=0,nrr2=0;
for(i=0;i<n;i++)
{
if(s[i]>='A'&&s[i]<='Z')
q=s[i]-'A';
if(s[i]>='a'&&s[i]<='z')
q=26+s[i]-'a';
if(s[i]>='0'&&s[i]<='9')
q=52+s[i]-'0';
nrr1=nrr1*62+q;
nrr2=nrr2*62+q;
nrr1%=n1;
nrr2%=n2;
}
if(nrr1==nr1&&nrr2==nr2)
{
cate++;
v[cate]=1;
}
for(i=1;i<=h-n;i++)
{
taiere(i-1);
if(s[i+n-1]>='A'&&s[i+n-1]<='Z')
q=s[i+n-1]-'A';
if(s[i+n-1]>='a'&&s[i+n-1]<='z')
q=26+s[i+n-1]-'a';
if(s[i+n-1]>='0'&&s[i+n-1]<='9')
q=52+s[i+n-1]-'0';
nrr1=nrr1*62+q;
nrr2=nrr2*62+q;
nrr1%=n1;
nrr2%=n2;
if(nrr1==nr1&&nrr2==nr2)
{
cate++;
v[cate]=i;
}
if(cate==1000)
break;
}
}
printf("%d\n",cate);
for(i=1;i<=cate;i++)
printf("%d ",v[i]);
return 0;
}