Pagini recente » Cod sursa (job #478527) | Cod sursa (job #1406058) | Cod sursa (job #999503) | Istoria paginii runda/locala/clasament | Cod sursa (job #1146327)
#include <cstdio>
#include <cstring>
#include <vector>
#define Nmax 2000005
#define P1 100007
#define P2 100021
#define X 123456
#define Y 654321
using namespace std;
char a[Nmax],b[Nmax];
int sol[Nmax];
int main()
{
int N,M,v1=0,v2=0,v3=0,v4=0,aux1=1,aux2=1,i;
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf("%s%s", (a+1),(b+1));
N=strlen(a+1); M=strlen(b+1);
for(i=1;i<=N;++i)
{
v1=(1LL*v1*X+a[i]-'0')%P1;
v2=(1LL*v2*Y+a[i]-'0')%P2;
}
for(i=1;i<=N;++i)
{
v3=(1LL*v3*X+b[i]-'0')%P1;
v4=(1LL*v4*Y+b[i]-'0')%P2;
}
for(i=1;i<N;++i)
{
aux1=(1LL*aux1*X)%P1;
aux2=(1LL*aux2*Y)%P2;
}
if(v3==v1 && v4==v2)
sol[++sol[0]]=0;
for(i=N+1;i<=M;++i)
{
v3=(((v3-(1LL*(b[i-N]-'0')*aux1)%P1+P1)%P1)*X+b[i]-'0')%P1;
v4=(((v4-(1LL*(b[i-N]-'0')*aux2)%P2+P2)%P2)*Y+b[i]-'0')%P2;
if(v3==v1 && v4==v2)
sol[++sol[0]]=i-N;
}
printf("%d\n", sol[0]);
for(i=1;i<=sol[0] && i<=1000;++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}