Pagini recente » Cod sursa (job #2057802) | Cod sursa (job #3124124) | Cod sursa (job #2684741) | Cod sursa (job #2567540) | Cod sursa (job #2287745)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int c[1002], o;
long long int p1, p2;
struct Hash{
long long n, m, p=1, rez=0;
int 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);
gets(a);
gets(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;
}