Pagini recente » Cod sursa (job #742833) | Cod sursa (job #396909) | Cod sursa (job #2214478) | Cod sursa (job #1863138) | Cod sursa (job #1235299)
#include <cstdio>
#include <cstring>
using namespace std;
const int mod1=100007,mod2=666013,p=79;
int sol[1010],n,n1,i,p1,p2,hash1,hash2,hashv1,hashv2,nr;
char v[2000010],v1[2000010];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s",v,v1);
n=strlen(v);
n1=strlen(v1);
if(n>n1)
{
printf("0");
return 0;
}
for(i=0;i<n;i++)
{
hashv1=(hashv1*p+v[i])%mod1;
hashv2=(hashv2*p+v[i])%mod2;
hash1=(hash1*p+v1[i])%mod1;
hash2=(hash2*p+v1[i])%mod2;
}
p1=p2=1;
for(i=1;i<n;i++)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
if(hash1==hashv1 && hash2==hashv2) sol[++nr]=0;
for(i=n;i<n1;i++)
{
hash1=((hash1-(p1*v1[i-n])%mod1+mod1)*p+v1[i])%mod1;
hash2=((hash2-(p2*v1[i-n])%mod2+mod2)*p+v1[i])%mod2;
if(hash1==hashv1 && hash2==hashv2)
{
nr++;
if(nr<=1000) sol[nr]=i-n+1;
}
}
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}