Pagini recente » Cod sursa (job #792789) | Cod sursa (job #247705) | Cod sursa (job #290426) | Cod sursa (job #1864396) | Cod sursa (job #3282598)
#include <fstream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int MOD=1e9+7;
long long int n,m,u,v,a[2000005],hash2[2000005],grad[50005],ans[2005],nr,hash1;
vector<int>g[50005];
queue<int>q;
string s1,s2;
int main()
{
cin>>s1;
cin>>s2;
n=s1.size();
m=s2.size();
a[0]=1;
for(int i=1;i<=2000005;i++)
a[i]=a[i-1]*127%MOD;
for(int i=0;i<n;i++)
hash1=(hash1*127+(s1[i]-'0'))%MOD;
for(int i=0;i<m;i++)
hash2[i+1]=(hash2[i]*127+(s2[i]-'0'))%MOD;
for(int i=n;i<=m;i++)
{
int k=(hash2[i]-(hash2[i-n]*a[n])%MOD+MOD)%MOD;
if(hash1==k)
{
nr++;
if(nr<=1000)
ans[nr]=i-n;
}
}
cout<<nr<<'\n';
nr=min(nr,1LL*1000);
for(int i=1; i<=nr; i++)
cout<<ans[i]<<' ';
return 0;
}