Pagini recente » Cod sursa (job #129971) | Cod sursa (job #1729224) | Cod sursa (job #2799155) | Cod sursa (job #1469941) | Cod sursa (job #855455)
Cod sursa(job #855455)
#include <cstdio>
#include <string.h>
#include<vector>
using namespace std;
#define nmax 2000001
#define baza 71
#define mod1 100007
#define mod2 100021
char a[nmax], b[nmax];
int m, n;
int h1, h2, pmax1, pmax2;
vector <int> gasit;
int main()
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s",&a,&b);
n=strlen(a);
m=strlen(b);
if (n>m) { printf("0\n"); return 0;}
pmax1=pmax2=1;
h1=h2=0;
for (i=0;i<n;++i)
{
h1=(h1*baza+a[i])%mod1;
h2=(h2*baza+a[i])%mod2;
if (i>0)
{ pmax1=(pmax1*baza)%mod1;
pmax2=(pmax2*baza)%mod2;}
}
int hb1=0,hb2=0;
for (i=0;i<n;++i)
{ hb1=(hb1*baza+b[i])%mod1;
hb2=(hb2*baza+b[i])%mod2;}
int nrgasit=0;
if (h1==hb1&&h2==hb2)
{gasit.push_back(0); nrgasit++;}
for (i=n;i<m;++i)
{
hb1=((hb1-(b[i-n]*pmax1)%mod1+mod1)*baza+b[i])%mod1;
hb2=((hb2-(b[i-n]*pmax2)%mod2+mod2)*baza+b[i])%mod2;
if (h1==hb1&&h2==hb2)
{gasit.push_back(i-n+1); nrgasit++;}
}
if (nrgasit!=0)
printf("%d\n", nrgasit);
int nr=gasit.size();
if (nr==0) printf("0\n");
else
{nr=nr%1000;
if (nr==0) nr=1000;
}
for (int i = 0; i <nr; i++)
printf("%d ",gasit[i]);
printf("\n");
return 0;
}