Pagini recente » Cod sursa (job #1732678) | Cod sursa (job #1380026) | Cod sursa (job #1413501) | Cod sursa (job #2730070) | Cod sursa (job #3236798)
#include <fstream>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
long long int t,n,i,j,m,x,y,s,sum,l,r,a[2000005],hash1,hash2[2000005],ans[1005],k,h,q,nr,p,maxi;
const int MOD=1e9+7;
string s1,s2;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>s1>>s2;
n=s1.size();
m=s2.size();
a[0]=1;
for(i=1; i<=2000000; i++)
a[i]=(a[i-1]*127)%MOD;
for(i=0; i<n; i++)
hash1=(hash1*127+(s1[i]-'0'))%MOD;
for(i=0; i<m; i++)
hash2[i+1]=(hash2[i]*127+(s2[i]-'0'))%MOD;
for(i=n; i<=m; i++)
{
q=(hash2[i]-(hash2[i-n]*a[n]%MOD)+MOD)%MOD;
if(q==hash1)
{
nr++;
if(nr<=1000)
ans[nr]=i-n;
}
}
cout<<nr<<'\n';
nr=min(nr,1LL*1000);
for(i=1; i<=nr; i++)
cout<<ans[i]<<' ';
return 0;
}