Pagini recente » Profilul lui Adi Craciun (deneo) | Autentificare | Cod sursa (job #71342) | Cod sursa (job #1193411) | Cod sursa (job #2876854)
#include <bits/stdc++.h>
#define MOD1 1000000007
#define MOD2 1000000009
std::ifstream cin("strmatch.in");
std::ofstream cout("strmatch.out");
char a[2000010],b[2000010];
long long ans[1010],am1,am2,bm1,bm2,pm1,pm2,l1,l2;
int main()
{
cin>>a>>b;
if(strlen(a)>strlen(b))
{
cout<<0;
return 0;
}
for(long long i=0;a[i];++i)
{
if('A'<=a[i]&&a[i]<='Z'||'0'<=a[i]&&a[i]<='9')
{
if('0'<=a[i]&&a[i]<='9')
a[i]=a[i]-'0'+'A'+52;
am1*=62;
am1+=(long long)(a[i]-'A');
am1%=MOD1;
am2*=62;
am2+=(long long)(a[i]-'A');
am2%=MOD2;
}
else
{
am1*=62;
am1+=(long long)(a[i]-'a'+26);
am1%=MOD1;
am2*=62;
am2+=(long long)(a[i]-'a'+26);
am2%=MOD2;
}
}
pm1=pm2=1;
for(long long i=0;a[i];++i)
{
pm1%=MOD1;
pm2%=MOD2;
if('a'<=b[i]&&b[i]<='z')
b[i]=b[i]-'a'+'A'+26;
else if('0'<=b[i]&&b[i]<='9')
b[i]=b[i]-'0'+'A'+52;
bm1*=62;
bm1+=b[i]-'A';
bm1%=MOD1;
bm2*=62;
bm2+=b[i]-'A';
bm2%=MOD2;
pm1*=62;
pm2*=62;
}
pm1/=62;
pm2/=62;
if(am1==bm1&&am2==bm2)
ans[++ans[0]]=0;
long long l=strlen(a);
for(long long i=l;b[i];++i)
{
if('a'<=b[i]&&b[i]<='z')
b[i]=b[i]-'a'+'A'+26;
else if('0'<=b[i]&&b[i]<='9')
b[i]=b[i]-'0'+'A'+52;
bm1=((bm1-(pm1*(b[i-l]-'A')%MOD1)%MOD1+MOD1)*62%MOD1+b[i]-'A'+MOD1)%MOD1;
bm2=((bm2-(pm2*(b[i-l]-'A')%MOD2)%MOD2+MOD2)*62%MOD2+b[i]-'A'+MOD2)%MOD2;
if(am1==bm1&&am2==bm2)
{
++ans[0];
if(ans[0]<=1000)
ans[ans[0]]=i-l+1;
}
}
cout<<ans[0]<<'\n';
ans[0]=std::min(1LL*1000,ans[0]);
for(long long i=1;i<=ans[0];++i)
cout<<ans[i]<<' ';
return 0;
}