Pagini recente » Cod sursa (job #1525881) | Cod sursa (job #1342757) | Istoria paginii runda/selectie_emag_mediu_2016_runda2 | Cod sursa (job #1006511) | Cod sursa (job #1484268)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013
#define b1 127
#define b2 131
#define mod1 1000000007
#define mod2 1000000021
using namespace std;
int n, m, i, j, h1, h2, H1, H2;
int q, r[1005];
int hsh1[2000005], hsh2[2000005], p1[2000005], p2[2000005];
char a[2000005], b[2000005];
int HASH1(int st, int dr)
{
int rez = hsh1[dr];
int x = (1LL * hsh1[st - 1] * p1[dr - st + 1]) % mod1;
rez -= x;
if(rez < 0)
rez += mod1;
return rez;
}
int HASH2(int st, int dr)
{
int rez = hsh2[dr];
int x = (1LL * hsh2[st - 1] * p2[dr - st + 1]) % mod2;
rez -= x;
if(rez < 0)
rez += mod2;
return rez;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a + 1); n = strlen(a + 1);
gets(b + 1); m = strlen(b + 1);
p1[0] = p2[0] = 1;
for(i = 1; i <= m; i++)
{
p1[i] = (1LL * p1[i - 1] * b1) % mod1;
p2[i] = (1LL * p2[i - 1] * b2) % mod2;
hsh1[i] = (1LL * hsh1[i - 1] * b1) % mod1;
hsh1[i] = (hsh1[i] + b[i]) % mod1;
hsh2[i] = (1LL * hsh2[i - 1] * b2) % mod2;
hsh2[i] = (hsh2[i] + b[i]) % mod2;
}
H1 = H2 = 0;
for(i = 1; i <= n; i++)
{
H1 = (1LL * H1 * b1) % mod1;
H1 = (H1 + a[i]) % mod1;
H2 = (1LL * H2 * b2) % mod2;
H2 = (H2 + a[i]) % mod2;
}
for(i = 1; i <= m - n + 1; i++)
{
h1 = HASH1(i, i + n - 1);
h2 = HASH2(i, i + n - 1);
if(H1 == h1 && H2 == h2)
{
q++;
if(q <= 1000)
r[q] = i - 1;
}
}
printf("%d\n", q);
for(i = 1; i <= q; i++)
printf("%d ", r[i]);
return 0;
}