Pagini recente » Cod sursa (job #2033909) | Cod sursa (job #2543949) | Cod sursa (job #190532) | Cod sursa (job #1992439) | Cod sursa (job #1235237)
#include <cstdio>
#include <cstring>
using namespace std;
const int mod1=100007,mod2=100021,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]-'0')%mod1;
hashv2=(hashv2*p+v[i]-'0')%mod2;
hash1=(hash1*p+v1[i]-'0')%mod1;
hash2=(hash2*p+v1[i]-'0')%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]-'0')+mod1)%mod1)*p+v1[i]-'0')%mod1;
hash2=(((hash2-p2*(v1[i-n]-'0')+mod2)%mod2)*p+v1[i]-'0')%mod2;
if(hash1==hashv1 && hash2==hashv2) if(nr<1000) sol[++nr]=i-n+1;
else nr++;
}
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}