Pagini recente » Cod sursa (job #1860372) | Cod sursa (job #2494285) | Cod sursa (job #1650070) | Cod sursa (job #2936150) | Cod sursa (job #2284308)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;
char p[NMAX], t[NMAX];
int n, m, nr, a[NMAX];
struct Hash
{
int n, m, power, hashh;
void init(char *s, int len)
{
power=1;
hashh=0;
for(int i=len-1; i>=0; i--)
{
hashh=(hashh+1LL*power*s[i])%m;
if(i)
power=(power*n)%m;
}
}
void roll(char toRemove, char toAdd)
{
hashh=(((hashh-1LL*toRemove*power+m)*n)%m+toAdd)%m;
}
};
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", p, t);
n=strlen(p);
m=strlen(t);
Hash pHash{3, 666013}, tHash{3, 666013};
Hash hHash{5, 17777777}, oHash{5, 17777777};
pHash.init(p, n);
tHash.init(t, n);
hHash.init(p, n);
oHash.init(t, n);
if(pHash.hashh == tHash.hashh && hHash.hashh == oHash.hashh)
{
a[++nr]=0;
}
for(int i=n; i<m; i++)
{
tHash.roll(t[i-n], t[i]);
oHash.roll(t[i-n], t[i]);
if(pHash.hashh == tHash.hashh && hHash.hashh == oHash.hashh)
{
a[++nr]=(i-n+1);
}
}
printf("%d\n", nr);
if(nr>1000)
nr=1000;
for(int i=1; i<=nr; i++)
{
printf("%d ", a[i]);
}
return 0;
}