Pagini recente » Cod sursa (job #2951924) | Cod sursa (job #818097) | Cod sursa (job #1618663) | Cod sursa (job #1648759) | Cod sursa (job #855435)
Cod sursa(job #855435)
#include <cstdio>
#include <string.h>
#include<vector>
using namespace std;
#define nmax 2000001
#define baza 61
#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++;}
}
printf("%d\n", nrgasit);
for (int i = 0; i <gasit.size()%1000; i++)
printf("%d ",gasit[i]);
printf("\n");
return 0;
}