Pagini recente » Cod sursa (job #1361116) | Cod sursa (job #1104121) | Cod sursa (job #25204) | Cod sursa (job #708904) | Cod sursa (job #3249689)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax=2e6+3, mod=100076969, baz=101;
int hsh[nmax], 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 nr*nr%mod;
return 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]=inv[i-1]*start%mod;
}
pwr[0] = 1;
pwr[1]=baz;
for(int i=2; i<nmax; i++)
{
pwr[i]=(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+=(x*pwr[i])%mod;
}
int lg=s.size(), n=s2.size();
sp[0]=convert(s2[0]);
for(int i=1; i<s2.size(); i++)
{
sp[i]=(sp[i-1]+convert(s2[i])*pwr[i])%mod;
}
int ans=0;
for(int i=lg-1; i<n; i++)
{
int sum=(sp[i]-(i - lg >= 0 ? sp[i-lg] : 0)+mod)%mod*inv[i-lg+1]%mod;
if(sum==hsa) {
ras.push_back(i-lg+1);
ans++;
}
}
cout<<ans<<'\n';
for(auto i:ras) cout<<i<<' ';
return 0;
}