Pagini recente » Cod sursa (job #2157949) | Cod sursa (job #1637529) | Cod sursa (job #539645) | Cod sursa (job #1816049) | Cod sursa (job #2284341)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;
char p[NMAX], t[NMAX];
long long n, m, nr, a[1005];
struct Hash
{
long long n, m, power, hashh;
void init(char *s, long long len)
{
power=1;
hashh=0;
for(long long 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, 1046527}, tHash{3, 1046527};
Hash hHash{5, 42589}, oHash{5, 42589};
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(long long 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)
{
if(nr<=1000)
a[++nr]=(i-n+1);
else
nr++;
}
}
printf("%lld\n", nr);
if(nr>1000)
nr=1000;
for(int i=1; i<=nr; i++)
{
printf("%lld ", a[i]);
}
return 0;
}