Pagini recente » Rating Mirela (mirelamimi) | Cod sursa (job #532766) | Cod sursa (job #1232092) | Cod sursa (job #1251791) | Cod sursa (job #3296280)
#include <bits/stdc++.h>
#define pb push_back
#define int 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=ans*n%mod;
n=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]=put[i-1]*p%mod;invput[i]=invput[i-1]*invp%mod;}
for(int i=1;i<=n;++i) pref[i]=(pref[i-1]+s[i]*put[i-1]%mod)%mod;
int hsh=0;
for(int j=1;j<=m;++j)
{
hsh=(hsh+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=x*invput[i-1]%mod;
if(x==hsh) sol.pb(i);
}
cout<<min((long long)sol.size(),1000ll)<<'\n';
for(auto x:sol) cout<<x-1<<" ";
}