Pagini recente » Cod sursa (job #2615139) | Cod sursa (job #224922) | Cod sursa (job #2612983) | Cod sursa (job #1427957) | Cod sursa (job #2876840)
#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(int i=0;a[i];++i)
{
if('a'<=a[i]&&a[i]<='z')
{
am1*=52;
am1+=a[i]-'a';
am1%=MOD1;
am2*=52;
am2+=a[i]-'a';
am2%=MOD2;
}
else
{
am1*=52;
am1+=a[i]-'A'+26;
am1%=MOD1;
am2*=52;
am2+=a[i]-'A'+26;
am2%=MOD2;
}
}
pm1=pm2=1;
for(int i=0;a[i];++i)
{
pm1%=MOD1;
pm2%=MOD2;
if('A'<=b[i]&&b[i]<='Z')
b[i]=b[i]-'A'+'a'+26;
bm1*=52;
bm1+=b[i]-'a';
bm1%=MOD1;
bm2*=52;
bm2+=b[i]-'a';
bm2%=MOD2;
pm1*=52;
pm2*=52;
}
pm1/=52;
pm2/=52;
if(am1==bm1&&am2==bm2)
ans[++ans[0]]=0;
long long l=strlen(a);
for(int i=l;b[i];++i)
{
if('A'<=b[i]&&b[i]<='Z')
b[i]=b[i]-'A'+'a'+26;
bm1=((bm1-(pm1*(b[i-l]-'a')%MOD1)%MOD1+MOD1)*52%MOD1+b[i]-'a'+MOD1)%MOD1;
bm2=((bm2-(pm2*(b[i-l]-'a')%MOD2)%MOD2+MOD2)*52%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(int i=1;i<=ans[0];++i)
cout<<ans[i]<<' ';
return 0;
}