Pagini recente » Cod sursa (job #2739789) | Cod sursa (job #2740016) | tema | Cod sursa (job #1016634) | Cod sursa (job #3296283)
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=2e6+5;int p=251,mod=1e9+7;
int put[N],invput[N];
int pref[N];
int binpow(int n, int e)
{
int ans=1;
while(e)
{
if(e&1) ans=1ll*ans*n%mod;
n=1ll*n*n%mod;
e>>=1;
}
return ans;
}
int inv(int x) {return binpow(x,mod-2);}
signed main()
{
ifstream cin("strmatch.in");ofstream cout("strmatch.out");
string s,t;
cin>>t>>s;
int n=s.size(),m=t.size();
s='?'+s;t='?'+t;
put[0]=1;invput[0]=inv(1);
int invp=inv(p);
for(int i=1;i<=n;++i) {put[i]=1ll*put[i-1]*p%mod;invput[i]=1ll*invput[i-1]*invp%mod;}
for(int i=1;i<=n;++i) pref[i]=(pref[i-1]+1ll*s[i]*put[i-1]%mod)%mod;
int hsh=0;
for(int j=1;j<=m;++j)
{
hsh=(hsh+1ll*t[j]*put[j-1]%mod)%mod;
}
vector<int> sol;
for(int i=1;i+m-1<=n;++i)
{
int x=(pref[i+m-1]-pref[i-1]+mod)%mod;
x=1ll*x*invput[i-1]%mod;
if(x==hsh) sol.pb(i);
}
cout<<min((int)sol.size(),1000)<<'\n';
for(auto x:sol) cout<<x-1<<" ";
}