Pagini recente » Cod sursa (job #862738) | Cod sursa (job #3178655) | Cod sursa (job #2887420) | Cod sursa (job #2602051) | Cod sursa (job #3199702)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005], b[2000005];
long long P1=37, mod1=1e9+13,P2=31,mod2=1e9+7;
long long sol[1001],hasha1,hasha2,hash1,hash2,hashb2[2000005],hashb1[2000005],p1[2000005],p2[2000005];
int n,m,nr;
int main()
{
f>>a>>b;
n=strlen(a);
m=strlen(b);
p1[0]=p2[0]=1;
for(int i=1; i<m; i++)
{
p1[i]=(p1[i-1]*P1);
p2[i]=(p2[i-1]*P2);
}
for(int i=0; i<n; i++)
{
hasha1=(hasha1+a[i]*p1[i]);
hasha2=(hasha2+a[i]*p2[i]);
}
hashb1[0]=hashb1[0]=b[0];
for(int i=1; i<m; i++)
{
hashb1[i]=(hashb1[i-1]+b[i]*p1[i]);
hashb2[i]=(hashb2[i-1]+b[i]*p2[i]);
}
for(int i=0; i<=m-n; i++)
{
if(i==0)hash1=hashb1[i+n-1],hash2=hashb2[i+n-1];
else hash1=(hashb1[i+n-1]-hashb1[i-1]),hash2=(hashb2[i+n-1]-hashb2[i-1]);
if((hasha1*p1[i])==hash1 && (hasha2*p2[i])==hash2)
{
nr++;
if(nr<=1000)
{
sol[nr]=i;
}
}
}
g<<nr<<'\n';
for(int i=1; i<=nr; i++)
{
g<<sol[i]<<' ';
}
return 0;
}