Pagini recente » Cod sursa (job #3186483) | Cod sursa (job #1346950) | Cod sursa (job #2628072) | Cod sursa (job #305976) | Cod sursa (job #3249714)
#include <bits/stdc++.h>
using namespace std;
const int nmax=2e6+3, mod=100076969, baz=103;
int hsa=0, pwr[nmax], inv[nmax], sp[nmax];
vector <int> ras;
int convert(char c)
{
if(c-'0'<=9) return (c-'0'+1);
if(c-'A'<=26) return (c-'A'+11);
return (c-'a'+11+26);
}
int exp(int x, int put)
{
if(put==0) return 1;
int nr=exp(x, put/2)%mod;
if(put%2==0) return 1LL*nr*nr%mod;
return 1LL*nr*nr%mod*x%mod;
}
signed main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int start=exp(baz, mod-2);
inv[0]=1;
inv[1]=start;
for(int i=2; i<nmax; i++)
{
inv[i]=1LL*inv[i-1]*start%mod;
}
pwr[0] = 1;
pwr[1]=baz;
for(int i=2; i<nmax; i++)
{
pwr[i]=(1LL*pwr[i-1]*baz)%mod;
}
string s, s2;
cin>>s>>s2;
for(int i=0; i<s.size(); i++)
{
int x=convert(s[i]);
(hsa+=(1LL*x*pwr[i])%mod)%=mod;
}
int lg=s.size(), n=s2.size();
sp[0]=convert(s2[0]);
for(int i=1; i<s2.size(); i++)
{
sp[i]=(1LL*sp[i-1]+1LL*convert(s2[i])*pwr[i])%mod;
}
int ans=0;
for(int i=lg-1; i<n; i++)
{
int sum=1LL*(sp[i]-(i - lg >= 0 ? sp[i-lg] : 0)+mod)%mod*inv[i-lg+1]%mod;
if(sum==hsa)
{
if(ans<1000)
ras.push_back(i-lg+1);
ans++;
}
}
cout<<ans<<'\n';
for(auto i:ras) cout<<i<<' ';
return 0;
}