Pagini recente » Cod sursa (job #1764178) | Cod sursa (job #2890366) | Cod sursa (job #2267942) | Cod sursa (job #1380693) | Cod sursa (job #1867515)
#include <cstdio>
#include <cstring>
#define mod 66029
#define mod1 10007
#define b1 101
#define b2 109
using namespace std;
char a[2000090],b[2000090];
int i,h1,h2,v1,v2,nr,c[1003],n,m,x,y,p,p1;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&a,&b);
m=strlen(a);
n=strlen(b);
if(m>n)printf("0");
else
{
p=p1=1;
for(i=0; i<strlen(a); i++)
{
h1=(h1*b1%mod+(int)a[i])%mod;
h2=(h2*b2%mod1+(int)a[i])%mod1;
v1=(v1*b1%mod+(int)b[i])%mod;
v2=(v2*b2%mod1+(int)b[i])%mod1;
if(i!=0)
{
p=(p*b1)%mod;
p1=(p1*b2)%mod1;
}
}
if(v1==h1 && v2==h2)
{
nr++;
c[nr]=0;
}
for(i=m; i<n; i++)
{
x=(int)b[i-m];
y=(int)b[i];
v1=(((v1-(x*p))%mod+mod)%mod*b1+y)%mod;
v2=(((v2-(x*p1))%mod1+mod1)%mod1*b2+y)%mod1;
if(v1==h1 && v2==h2)
{
nr++;
if(nr<=1000)
c[nr]=i-strlen(a)+1;
}
}
printf("%d\n",nr);
for(i=1; i<=nr && i<=1000; i++)printf("%d ",c[i]);
}
return 0;
}