Pagini recente » Cod sursa (job #1960791) | Cod sursa (job #3221860) | Cod sursa (job #104696) | Cod sursa (job #528681) | Cod sursa (job #2284581)
#include <cstdio>
#include <cstring>
using namespace std;
long long int n1 = 31, m1 = 40099;
long long int n2 = 53, m2 = 319993;
long long int h1, h2, h3, h4;
int nr;
int indici[2000005];
char c[2000005];
char s[2000005];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", c, s);
int k1 = strlen(c);
int k2 = strlen(s);
long long int putere1 = 1;
long long int putere2 = 1;
for (int i = k1-1; i >= 0; i--)
{
h1 = (h1 + c[i]*putere1)%m1;
h3 = (h3 + s[i]*putere1)%m1;
if (i > 0) putere1 = (putere1*n1)%m1;
h2 = (h2 + c[i]*putere2)%m2;
h4 = (h4 + s[i]*putere2)%m2;
if (i > 0) putere2 = (putere2*n2)%m2;
}
if (h1 == h3 && h2 == h4)
{
nr++;
indici[0] = 1;
}
for (int i = k1; i < k2; i++)
{
h3 = ((h3 - (s[i-k1]*putere1) % m1 + m1)*n1+s[i])%m1;
h4 = ((h4 - (s[i-k1]*putere2) % m2 + m2)*n2+s[i])%m2;
if (h1 == h3 && h2 == h4)
{
nr++;
indici[i-k1+1] = 1;
}
}
printf("%d\n", nr);
if (nr > 1000)
nr = 1000;
int j = 0;
for (int i = 0; j < nr; i++)
if (indici[i] == 1)
{
printf("%d ", i);
j++;
}
return 0;
}