Pagini recente » Cod sursa (job #1890866) | Cod sursa (job #2813914) | Cod sursa (job #2253341) | Cod sursa (job #2425606) | Cod sursa (job #2287753)
#include <cstdio>
#include <string.h>
using namespace std;
char a[2000001], b[2000001];
int c[1002], o;
struct Hash{
int n, m;
long long p=1, rez=0;
long long h1(char *a, int l)
{
p = 1;
rez=0;
for(int i=l-1; i>=0; i--)
{
rez = (rez + (a[i]*p)%m)%m;
p = (p * n)%m;
}
p/=n;
return rez;
}
void roll(char toRemove, char toAdd)
{
rez=(((rez-(1LL*toRemove*p)%m+m)*n)%m+toAdd)%m;
}
};
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", a, b);
int l1 = strlen(a), l2 = strlen(b);
Hash tc1, tc2;
Hash c1, c2;
tc1.n = 31;
tc1.m = 40099;
c1.n = 31;
c1.m = 40099;
tc2.n = 53;
tc2.m = 319993;
c2.n = 53;
c2.m = 319993;
tc1.h1(a, l1);
tc2.h1(a, l1);
c1.h1(b, l1);
c2.h1(b, l1);
if(tc1.rez == c1.rez && tc2.rez == c2.rez)
{
c[o++] = 0;
}
for(int i=l1; i<l2; i++)
{
c1.roll(b[i-l1], b[i]);
c2.roll(b[i-l1], b[i]);
if(tc1.rez == c1.rez && tc2.rez == c2.rez)
{
if(o < 1000)
c[o] = i-l1+1;
o++;
}
}
printf("%d\n", o);
if(o > 999)
for(int i=0; i<1000; i++)
printf("%d ", c[i]);
else for(int i=0; i<o; i++)
printf("%d ", c[i]);
return 0;
}