Pagini recente » Cod sursa (job #3175332) | Cod sursa (job #1536321) | Cod sursa (job #195646) | Cod sursa (job #1232627) | Cod sursa (job #3199722)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005], b[2000005];
long long P=37, mod=1e9+13;
long long sol[1001],hasha,hash1,hashb[2000005],p[2000005];
int n,m,nr;
int main()
{
f>>a>>b;
n=strlen(a);
m=strlen(b);
p[0]=1;
for(int i=1; i<m; i++)
{
p[i]=(p[i-1]*P)%mod;
}
for(int i=0; i<n; i++)
{
hasha=(hasha+a[i]*p[i])%mod;
}
hashb[0]=b[0];
for(int i=1; i<m; i++)
{
hashb[i]=(hashb[i-1]+b[i]*p[i])%mod;
}
for(int i=0; i<=m-n; i++)
{
if(i==0)hash1=hashb[i+n-1];
else hash1=(hashb[i+n-1]-hashb[i-1]+mod)%mod;
if((hasha*p[i])%mod==hash1)
{
nr++;
if(nr<=1000)
{
sol[nr]=i;
}
}
}
g<<nr<<'\n';
for(int i=1; i<=nr; i++)
{
g<<sol[i]<<' ';
}
return 0;
}